×

A branch-and-bound algorithm for the coupled task problem. (English) Zbl 1302.90132

Summary: The coupled task problem is to schedule jobs on a single machine where each job consists of two subtasks and where the second subtask has to be started after a given time interval with respect to the first one. The problem has several applications and is NP-hard. In this paper we present a branch-and-bound algorithm for this problem and compare its performance with four integer programming models.

MSC:

90C10 Integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ageev AA, Baburin AE (2007) Approximation algorithms for UET scheduling problems with exact delays. Oper Res Lett 25:533-540 · Zbl 1149.90337 · doi:10.1016/j.orl.2006.09.006
[2] Ahr D, Békési J, Galambos G, Oswald M, Reinelt G (2004) An exact algorithm for scheduling identical coupled tasks. Math Methods Oper Res 59:193-203 · Zbl 1138.90390 · doi:10.1007/s001860300328
[3] Blazewicz J, Ecker K, Kis T, Tanas M (2001) A note on the complexity of scheduling coupled tasks on a single processor. J Brazilian Comput Soc 7:23-26 · doi:10.1590/S0104-65002001000200004
[4] Elshafei M, Sherali HD, Smith JC (2004) Radar pulse interleaving for multi-target tracking. Nav Res Logist 51(1):72-94 · Zbl 1055.90096 · doi:10.1002/nav.10103
[5] Li H, Zhao H (2007) Scheduling coupled-tasks on a single machine. In: IEEE symposium on computational intelligence in scheduling SCIS ’07, pp 137-142 · Zbl 1149.90337
[6] Orman AJ, Potts CN (1997) On the complexity of coupled-task scheduling. Discret Appl Math 72:141-154 · Zbl 0873.90053 · doi:10.1016/S0166-218X(96)00041-8
[7] Orman AJ, Potts CN, Shahani AK, Moore AR (1996) Scheduling for a multifunction phased array radar system. Eur J Oper Res 90:13-25 · Zbl 0916.90153 · doi:10.1016/0377-2217(95)00307-X
[8] Potts CN, Whitehead JD (2007) Heuristics for a coupled-operation scheduling problem. J Oper Res Soc 58:1375-1388 · Zbl 1177.90179 · doi:10.1057/palgrave.jors.2602272
[9] Sherali HD, Smith JC (2005) Interleaving two-phased jobs on a single machine with application to radar pulse interleaving. Discret Optim 2:348-361 · Zbl 1175.90192 · doi:10.1016/j.disopt.2005.08.002
[10] Tanas M, Blazewicz J, Ecker K (2007) Polynomial time algorithm for coupled tasks scheduling problem. In: Blazewicz J, Ecker K, Hammer B (eds) ICOLE 2007. Lessach, Austria. Report IfI-07-03, TU Clausthal, pp 76-69 · Zbl 0916.90153
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.