A branch-and-bound algorithm for the two-machine total completion time flowshop problem subject to release dates

Akkan C, Karabati S (2004) The two-machine flowshop total completion time problem: improved lower bounds and a branch-and-bound algorithm. Eur J Oper Res 159(2):420–429 Baker KR (1974) Introduction to sequencing and scheduling. Wiley, New York Bansal SP (1977) Minimizing the sum of completion times of n jobs over m machines in a flow shop. Am Inst Ind Eng Trans 9(3):306–311 Chalghoumi S, Mehdi M, Ladhari T (2013) A new lower bound for minimising the total completion time in a two-machine flow shop under release dates. In: IEEE international conference on modeling, simulation and applied optimization, Hammamet, April 28–30, 2013, pp 1–4 Chung CS, Flynn J, Kirca O (2002) A branch-and-bound algorithm to minimize the total flow time for m-machine permutation flowshop problems. Int J Prod Econ 79(3):185–196 Della Croce F, Narayan V, Tadei R (1996) The two-machine total completion time flowshop problem. Eur J Oper Res 90(2):227–237 Della Croce F, Ghirardi M, Tadei R (2002) An improved branch-and-bound algorithm for the two machine total completion time flowshop problem. Eur J Oper Res 139(2):293–301 Della Croce F, T’Kindt V (2003) Improving the preemptive bound for the one-machine dynamic total completion time scheduling problem. Oper Res Lett 31(2):142–148 French S (1982) Sequencing and scheduling: an introduction to the mathematics of the job-shop. Ellis Horwood, Chichester Harchol-Balter H, Bansal N, Schroeder B, Agrawal M (2001) SRPT Scheduling for web servers. Lecture notes in computer science, chapter in job scheduling strategies for parallel processing. Springer, pp 11–20 Haouari M, Kharbeche M (2013) An assignment-based lower bound for a class of two-machine flow shop problems. Comput Oper Res 40(7):1693–1699 Hoogeveen JA, Van de Velde S (1995) Minimizing total completion and maximum cost simultaneously is solvable in polynomial time. Oper Res Lett 17(5):205–208 Hoogeveen H, Van Norden L, Van de Velde S (2006) Lower bounds for minimizing total completion time in a two-machine flow shop. J Sched 9(6):559–568 Ignall E, Schrage L (1965) Application of the branch-and-bound technique to some flowshop scheduling problems. Oper Res 13(3):400–412 Jouglet A, Baptiste P, Carlier J (2004) Branch-and-bound algorithms for total weighted tardiness. In: Leung JYT (ed) Handbook of scheduling: algorithms, models and performance analysis. CRC Press, FL, USA Kellerer H, Tautenhahn T, Woeginger GJ (1999) Approximability and non approximability results for minimizing total flow time on a single machine. SIAM J Comput 28(4):1155–1166 Kooli A, Serairi M (2013) An assignment based lower bound for the single machine with unequal release dates. In: 11th Workshop on models and algorithms for planning and scheduling problems, Pont à Mousson, 23–28 June, 2013 Kooli A, Serairi M (2014) A mixed integer programming approach for the single machine problem with unequal release dates. Comput Oper Res 51:323–330 Ladhari T, Rakrouki MA (2009) Heuristics and lower bounds for minimizing the total completion time in a two-machine flowshop. Int J Prod Econ 122(2):678–691 Leonardi S, Raz D (1997) Approximating total flow time on parallel machines. J Comput Syst Sci 73(6):875–891 Nawaz M, Enscore EE, Ham I (1983) A heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem. OMEGA 11(1):91–96 Pinedo M (2008) Scheduling: theory, algorithms, and systems. Springer, New York Potts CN, Van Wassenhove LN (1985) A branch-and-bound algorithm for the total weighted tardiness problem. Oper Res 33(2):363–377 Rakrouki MA, Ladhari T (2009) A branch-and-bound algorithm for minimizing the total completion time in two-machine flowshop problem subject to release dates. In: IEEE international conference on computers & industrial engineering, University of Technology of Troyes, July 6–8, 2009, pp 80–85 Rinnooy Kan AHG (1976) Machine sequencing problem: classification, complexity and computation. Nijhoff, The Hague Szwarc W (1983) The flow shop problem with mean completion time criterion. IIE Trans 15(2):172–176 T’Kindt V, Della Croce F, Esswein C (2004) Revisiting branch and bound search strategies for machine scheduling problems. J Sched 7(6):429–440 Van de Velde S (1990) Minimizing the sum of job completion times in the two-machine flowshop by Lagrangian relaxation. Ann Oper Res 26(1):257–268