×

On scheduling a single machine to minimize a piecewise linear objective function: a compact MIP formulation. (English) Zbl 1182.90040

Summary: We study the scheduling situation in which a set of jobs subjected to release dates and deadlines are to be performed on a single machine. The objective is to minimize a piecewise linear objective function \(\sum _j F_j\) where \(F_j(C_j)\) corresponds to the cost of the completion of job \(j\) at time \(C_j\). This class of function is very large and thus interesting both from a theoretical and practical point of view: It can be used to model total (weighted) completion time, total (weighted) tardiness, earliness and tardiness, etc. We introduce a new Mixed Integer Program (MIP) based on time interval decomposition. Our MIP is closely related to the well-known time-indexed MIP formulation but uses much less variables and constraints. Experiments on academic benchmarks as well as on real-life industrial problems show that our generic MIP formulation is efficient.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming

Software:

OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdul-Razacq, A survey of algorithms for the single machine total weighted tardiness scheduling problem, Discr Appl Mathe 26 pp 235– (1990)
[2] Akturk, An exact approach to minimizing total weighted tardiness with release dates, IIE Trans 32 pp 1091– (2000)
[3] Akturk, A new dominance rule to minimize total weighted tardiness with unequal release dates, Eur J Operation Res 135 pp 394– (2001) · Zbl 1051.90013
[4] Baptiste, Polynomial time algorithms for minimizing the weighted number of late jobs on a singlemachine when processing times are equal, J Scheduling 2 pp 245– (1999) · Zbl 0971.90026
[5] Baptiste, Scheduling equal-length jobs on identical parallel machines, Discr Appl Mathe 103 pp 21– (2000) · Zbl 0971.90027
[6] Baptiste, A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates, Eur J Operation Res 158 pp 595– (2004) · Zbl 1056.90054
[7] Ph. Baptiste, C. Le Pape, and L. Peridy, ” Global constraints for partial csps: A case study of resource and due-date constraints,” in: Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming, Pisa, 1998.
[8] Baptiste, A branch and bound to mininimze the number of late jobs on a single machine with release time constraints, Eur Operation Res 144 pp 1– (2003) · Zbl 1037.90022 · doi:10.1016/S0377-2217(01)00353-8
[9] J. E. Beasley, Or-library, Available at: http://people.brunel.ac.uk/mastjjb/jeb/info.html.
[10] Belouadah, Scheduling with release dates on a single machine to minimize total weighted completion time, Discr Appl Mathe 36 pp 213– (1992) · Zbl 0757.90032
[11] Bianco, Scheduling of a single machine to minimize total weighted completion time subject to release dates, Naval Res Logistics 29 pp 151– (1982) · Zbl 0539.90044
[12] Bigras, Time-indexed formulations and the total weighted tardiness problem, INFORMS J Comp · Zbl 1243.90057
[13] Bowman, The schedule-sequencing problem, Oper Res 7 pp 621– (1959) · Zbl 1255.90059
[14] Brucker, Scheduling algorithms (2001) · doi:10.1007/978-3-662-04550-3
[15] Brucker, Scheduling jobs with equal processing times and time windows on identical parallel machines, J Scheduling 11 pp 229– (2008) · Zbl 1168.90426
[16] Chand, Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm, Naval Res Logistics 43 pp 709– (1996) · Zbl 0868.90062
[17] Chandra, On n|1|F dynamic determistic systems, Naval Res Logistics 26 pp 537– (1979)
[18] Chang, On decomposition of the total tardiness problem, Operat Res Lett 17 pp 221– (1995) · Zbl 0858.90072
[19] H. Chen, C. Chu, and J. M. Proth, A branch and bound method to minimize total weighted earliness and tardiness with different due dates, Research Rep No. 2495, INRIA, France, 1995.
[20] Chu, A branch and bound algorithm to minimize total flow time with unequal release dates, Naval Res Logistics 39 pp 859– (1991) · Zbl 0766.90039
[21] Chu, A branch and bound algorithm to minimize total tardiness with different release dates, Naval Res Logistics 39 pp 265– (1992) · Zbl 0762.90035
[22] Chu, Efficient heuristics to minimize total flow time with release dates, Operat Res Lett 12 pp 321– (1992) · Zbl 0769.90047
[23] Chu, Some new efficient methods to solve the n|1|ri| Ti scheduling problem, Eur J Operat Res 58 pp 404– (1991)
[24] S. Dauzère-Pérès, M. Sevaux, A branch and bound method to minimize the number of late jobs on a single machine, Technical report, Research report 98/5/AUTO, Ecole des Mines de Nantes, 1998. · Zbl 1053.90046
[25] Deogun, On scheduling with ready times to minimize mean flow time, Comput J 26 pp 320– (1983) · Zbl 0523.68029 · doi:10.1093/comjnl/26.4.320
[26] Dessouky, Sequencing jobs with unequal ready times to minimize mean flow time, SIAM J Comput 10 pp 192– (1981) · Zbl 0454.68010
[27] Du, Minimizing total tardiness on one processor is NP-Hard, Mathe Operat Res 15 pp 483– (1990) · Zbl 0714.90052
[28] Dyer, Formulating the single machine sequencing problem with release dates as mixed integer program, Disc App Math 26 pp 255– (1990) · Zbl 0694.90060
[29] Emmons, One-machine sequencing to minimize certain functions of job tardiness, Operat Res 17 pp 701– (1969) · Zbl 0176.50005
[30] Sourd, A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem, J Scheduling 11 pp 49– (2008) · Zbl 1168.90471
[31] Hariri, An algorithm for single machine sequencing with release dates to minimize total weighted completion time, Discr Appl Mathe 5 pp 99– (1983) · Zbl 0498.90044
[32] Jouglet, Handbook of scheduling: Algorithms, models and performance analysis (2004)
[33] Wolsey, A time-indexed formulation of non-preemptive single-macine scheduling problems, Math Prog 54 pp 353– (1992)
[34] Labetoulle, Progress in combinatorial Optimization (1984)
[35] Lawler, A pseudo-polynomial algorithm for sequencing jobs to minimize total tardiness, Ann Discr Mathe 1 pp 331– (1977) · Zbl 0353.68071
[36] C. Le Pape, and A. Robert, Jeux de données pour l’évaluation d’algorithmes de planification et ordonnacement, in: Livre des résumés séléctionnés lors de la conférence conjointe FRANCORO V/ROADEF 2007, 20-23 fevrier, Grenoble, 2007.
[37] Schulz, Polyhedral approaches to machine scheduling pp 408– (1994)
[38] M’Hallah, Minimizing the weighted number of tardy jobs on a single machine with release dates, Eur J Operat Res 176 pp 727– (2007)
[39] Nemhauser, Combinatorial optimization: New frontiers in the theory and practice pp 63– (1992) · doi:10.1007/978-3-642-77489-8_4
[40] W. Nuijten, T. Bousonville, F. Focacci, D. Godard, and C. Le Pape, ” Towards an industrial manufacturing scheduling problem and test bed,” in: Proceedings of the Ninth Workshop on Project Management and Scheduling, Nancy, 2004.
[41] Pan, On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems, Mathe Prog 110 pp 543– (2006)
[42] Pan, New hybrid optimization algorithms for machine scheduling problems, IEEE Trans Automat Sci Eng 5 pp 337– (2008)
[43] Potts, A decomposition algorithm for the single machine total tardiness problem, Operat Res Lett 26 pp 177– (1982) · Zbl 0508.90045
[44] Pritsker, Multiproject scheduling with limited resources: A zero-one programming approach, Management Sci 16 pp 93– (1969)
[45] Rachamadugu, A note on weighted tardiness problem, Operat Res 35 pp 450– (1987) · Zbl 0627.90053
[46] G. L. Ragatz, A branch-and-bound method for minimum tardiness sequencing on a single processor with sequence dependent setup times, in: Twenty-fourth Annual Meeting of the Decison Sciences Institute, New Orleans, November 1993.
[47] Redwine, A mixed integer programming model for scheduling orders in a steel mill, J Optim Theory Appl 14 pp 305– (1974) · Zbl 0268.90046
[48] G. Rinaldi, and A. Sassano, On a job scheduling problem with different ready times: Some properties and a new algorithm to determine the optimal solution, Operation Research, 1977. Rapporto dell’Ist. di Automatica dell’Universita di Roma e del C.S.S.C.C.A.-C.N.R.R, Report R.77-24.
[49] Rinnooy Kan, Machine sequencing problem: classification, complexity and computation (1976)
[50] Rinnooy Kan, Minimizing total costs in one-machine scheduling, Operat Res 23 pp 908– (1975) · Zbl 0316.90033
[51] R. Sadykov, ” A hybrid branch-and-cut algorithm for the one-machine scheduling problem,” in: Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems, Nice, France, April 2004. · Zbl 1094.90562
[52] Smith, Various optimizers for single stage production, Naval Res Logistics Quart 3 pp 59– (1956)
[53] A. Souissi, I. Kacem, and C. Chu, ” New lower bound for minimizing total tardiness on a single machine with sequence-dependent setup times,” in: Proceedings of the Ninth International Conference on Project Management and Scheduling, PMS04, Nancy, France, April 2004.
[54] Szwarc, Solution of the single machine total tardiness problem, J Scheduling 2 pp 55– (1999) · Zbl 0963.90029
[55] Szwarc, Algorithmic paradoxes of the single machine total tardiness problem, J Scheduling 4 pp 93– (2001) · Zbl 0994.90076
[56] J. M. Van den Akker, G. Diepen, and J. A. Hoogeveen, Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs, Technical report UU-CS-2005-054, Utrecht University, 2005. · Zbl 1208.90083
[57] Van den Akker, A polyhedral approach to single-machine scheduling problems, Math Prog 85 pp 541– (1999) · Zbl 1072.90523
[58] Verma, Single-machine scheduling of unit-time jobs with earliness and tardiness penalties, Math Oper Res 23 pp 930– (1998) · Zbl 0977.90017
[59] Yau, New solution approaches to the general single machine earliness-tardiness problem, IEEE Trans Auto Sci Eng 5 pp 349– (2008)
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.