Abstract
This paper presents a Branch, Bound, and Remember (BB&R) exact algorithm using the Cyclic Best First Search (CBFS) exploration strategy for solving the \({1|ST_{sd}|\sum T_{i}}\) scheduling problem, a single machine scheduling problem with sequence dependent setup times where the objective is to find a schedule with minimum total tardiness. The BB&R algorithm incorporates memory-based dominance rules to reduce the solution search space. The algorithm creates schedules in the reverse direction for problems where fewer than half the jobs are expected to be tardy. In addition, a branch and bound algorithm is used to efficiently compute tighter lower bounds for the problem. This paper also presents a counterexample for a previously reported exact algorithm in Luo and Chu (Appl Math Comput 183(1):575–588, 2006) and Luo et al. (Int J Prod Res 44(17):3367–3378, 2006). Computational experiments demonstrate that the algorithm is two orders of magnitude faster than the fastest exact algorithm that has appeared in the literature. Computational experiments on two sets of benchmark problems demonstrate that the CBFS search exploration strategy can be used as an effective heuristic on problems that are too large to solve to optimality.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Allahverdi A., Ng C.T., Cheng T.C.E., Kovalyov M.Y.: A survey of scheduling problems with setup time or cost. Eur. J. Oper. Res. 187(3), 985–1032 (2008)
Armentano V.A., Mazzini R.: A genetic algorithm for scheduling on a single machine with set-up times and due dates. Prod. Plan. Control 11(7), 713–720 (2000)
Bedworth D., Bailey J.: Integrated Production Control Systems: Management, Analysis Design. Wiley, New York (1987)
Brucker P.: Scheduling Algorithms, 2nd edn. Springer, Heidelberg (1999)
Chang S., Lu Q., Tang G., Yu W.: On decomposition of the total tardiness problem. Oper. Res. 17(5), 221–229 (1995)
Du J., Leung J.Y.-T.: Minimizing total tardiness on one machine is NP-hard. Math. Oper. Res. 15(3), 483–495 (1990)
Easton F.F.: A dynamic program with fathoming and dynamic upper bounds for the assembly line balancing problem. Comput. Oper. Res. 17(2), 163–175 (1990)
Gagné C., Price W.L., Gravel M.: Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times. J. Oper. Res. Soc. 53(8), 895–906 (2002)
Gagné C., Gravel M., Price W.L.: Using metaheuristic compromise programming for the solution of multi-objective scheduling problems. J. Oper. Res. Soc. 56(6), 687–698 (2005)
Garfinkel R., Nemhauser G.: Integer Programming. Wiley, New York (1972)
Graham R., Lawler E., Lenstra J., Rinnooy Kan A.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287–326 (1979)
Gupta S.R., Smith J.S.: Algorithms for single machine total tardiness scheduling with sequence dependent setups. Eur. J. Oper. Res. 175(2), 722–739 (2006)
Jouglet A., Baptiste P., Carlier J.: Branch-and-bound algorithms for total weighted tardiness. In: Leung, J.Y-T. (eds) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, Boca Raton (2004)
Kao G.K., Sewell E.C., Jacobson S.H.: A branch, bound, and remember algorithm for the \({1|r_{i}|\sum t_{i} }\) scheduling problem. J. Sched. 12(2), 163–175 (2009)
Kao, G.K., Sewell, E.C., Jacobson, S.H., Hall, S.N.: New Dominance Rules and Exploration Strategies for the \({1|r_{i}|\sum U_{i}}\) Scheduling Problem. Technical Report, Department of Computer Science, University of Illinois at Urbana Champaign (2010)
Lawler E.L.: A pseudo-polynomial algorithm for sequencing jobs to minimize total tardiness. Ann. Discret. Math. 1, 331–342 (1977)
Lee Y.H., Bhaskaran K., Pinedo M.: A heuristic to minimize the total weighted tardiness with sequence dependent setups. IIE Trans. 29(1), 45–52 (1997)
Liao C.J., Juan H.C.: An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Comput. Oper. Res. 34, 1899–1909 (2007)
Lin S.W., Ying K.C.: Solving single-machine total weighted tardiness problems with sequence-dependent setup times by meta-heuristics. Int. J. Adv. Manuf. Technol. 34(11), 1183–1190 (2007)
Lin S.W., Ying K.C.: A hybrid approach for single-machine tardiness problems with sequence-dependent setup times. J. Oper. Res. Soc. 59(8), 1109–1119 (2008)
Luo X., Chu F.: A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness. Appl. Math. Comput. 183(1), 575–588 (2006)
Luo X., Chu C.: A branch and bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness. Eur. J. Oper. Res. 180(1), 68–81 (2007)
Luo X., Chu C., Wang C.: Some dominance properties for single-machine tardiness problem with sequence-dependent setup. Int. J. Prod. Res. 44(17), 3367–3378 (2006)
Michie D.: Memo functions and machine learning. Nature 218, 19–22 (1968)
Morin T., Marsten R.: Branch-and-bound strategies for dynamic programming. Oper. Res. 24(4), 611–627 (1976)
Panwalkar S.S., Dudek R.A., Smith M.L.: Sequencing research and the industrial scheduling problem. In: Elmaghraby, E. (eds) Symposium on the Theory of Scheduling and its Applications, pp. 29–38. Springer, Berlin (1973)
Pardalos, P.M. (eds): Complexity in Numerical Optimization. World Scientific, Singapore (1993)
Pardalos, P.M., Resende, M.G.C. (eds): Handbook of Applied Optimization. Oxford University Press, New York (2002)
Potts C.N., Van Wassenhove L.N.: A decomposition algorithm for the single machine total tardiness problem. Oper. Res. Lett. 1(5), 177–182 (1982)
Ragatz, G.L.: A branch and bound method for minimum tardiness sequencing on a single processor with sequence dependent setup times. In: Proceedings of the 24th Annual Meeting of the Decision Sciences Institute, pp. 1375–1377 (1993)
Rubin P.A., Ragatz G.L.: Scheduling in a sequence dependent setup environment with genetic search. Comput. Oper. Res. 22(1), 85–99 (1995)
Sellers, D.W.: A survey of approaches to the job shop scheduling problem. In: 28th Southeastern Symposium on System Theory, pp. 396–400. IEEE Computer Society, Washington (1996)
Souissi, A., Chu, C.: Minimizing total tardiness on a single machine with sequence-dependent setup times. In: 2004 IEEE International Conference on Systems, Man and Cybernetics, pp. 1481–1485. IEEE Computer Society, Hague (2004)
Szwarc W., Della Croce F., Grosso A.: Solution of the single-machine total tardiness problem. J. Sched. 2, 55–71 (1999)
Tan K.C., Narasimhan R.: Minimizing tardiness on a single processor with sequence dependent setup times: a simulated annealing approach. Omega 25(6), 619–634 (1997)
Tan K.C., Narasimhan R., Rubin P.A., Ragatz G.L.: A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times. Omega 28(3), 313–326 (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sewell, E.C., Sauppe, J.J., Morrison, D.R. et al. A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times. J Glob Optim 54, 791–812 (2012). https://doi.org/10.1007/s10898-011-9793-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-011-9793-z