Skip to main content
SpringerLink
Log in

A branch-and-bound algorithm for the coupled task problem

  • Original Article
  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  • Ageev AA, Baburin AE (2007) Approximation algorithms for UET scheduling problems with exact delays. Oper Res Lett 25:533–540

    Article  MathSciNet  Google Scholar 

  • 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

    Article  MATH  MathSciNet  Google Scholar 

  • 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

    Article  Google Scholar 

  • Elshafei M, Sherali HD, Smith JC (2004) Radar pulse interleaving for multi-target tracking. Nav Res Logist 51(1):72–94

    Article  MATH  MathSciNet  Google Scholar 

  • 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

  • Orman AJ, Potts CN (1997) On the complexity of coupled-task scheduling. Discret Appl Math 72:141–154

    Article  MATH  MathSciNet  Google Scholar 

  • Orman AJ, Potts CN, Shahani AK, Moore AR (1996) Scheduling for a multifunction phased array radar system. Eur J Oper Res 90:13–25

    Article  MATH  Google Scholar 

  • Potts CN, Whitehead JD (2007) Heuristics for a coupled-operation scheduling problem. J Oper Res Soc 58:1375–1388

    Article  MATH  Google Scholar 

  • Sherali HD, Smith JC (2005) Interleaving two-phased jobs on a single machine with application to radar pulse interleaving. Discret Optim 2:348–361

    Article  MATH  MathSciNet  Google Scholar 

  • 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

Download references

Acknowledgments

We would like to thank two anonymous referees for very helpful and extensive comments and suggestions. They improved this paper considerably.

Author information

Authors and Affiliations

  1. Department of Computer Sciences, Juhász Gyula Teacher Training Faculty, University of Szeged, Boldogasszony sgt. 3, Szeged , 6701, Hungary

    József Békési & Gábor Galambos

  2. Fakultät für Mathematik und Informatik, Institut für Informatik, Universität Heidelberg, Im Neuenheimer Feld 368, 69120 , Heidelberg, Germany

    Michael N. Jung, Marcus Oswald & Gerhard Reinelt

Authors
  1. József Békési
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gábor Galambos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael N. Jung
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Marcus Oswald
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Gerhard Reinelt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gerhard Reinelt.

Additional information

József Békési and Gábor Galambos received the support from the European Union and the European Social Fund through project “Supercomputer, the national virtual lab”, Grant No.: TAMOP-4.2.2.C-11/1/KONV-2012-0010.

Michael N. Jung, Marcus Oswald and Gerhard Reinelt received the support from DAAD exchange program 324 PPP-Ungarn.

Appendix

Appendix

See Appendix Tables 2, 3, 4, 5, 6, 7.

Table 2 The table contains the results for 40 randomly generated instances
Full size table
Table 3 The table contains the results for 40 randomly generated instances
Full size table
Table 4 The table contains the results for 40 randomly generated instances
Full size table
Table 5 The table contains the results for 40 randomly generated instances
Full size table
Table 6 The table contains the results for 40 randomly generated instances
Full size table
Table 7 The table contains the results for 40 randomly generated instances
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Békési, J., Galambos, G., Jung, M.N. et al. A branch-and-bound algorithm for the coupled task problem. Math Meth Oper Res 80, 47–81 (2014). https://doi.org/10.1007/s00186-014-0469-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00186-014-0469-6

Keywords

Search

Navigation