Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs. (English) Zbl 1054.90028
Summary: We consider the problem of scheduling customer orders in a flow shop with the objective of minimizing the sum of tardiness, earliness (finished goods inventory holding), and intermediate (work-in-process) inventory holding costs. We formulate this problem as an integer program, and based on approximate solutions to two different, but closely related, Dantzig-Wolfe reformulations, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig-Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two different lower bounds on the optimal integer solution, together with intuitive approaches for obtaining near-optimal feasible integer solutions. To the best of our knowledge, this is the first paper that applies column generation to a scheduling problem with different types of strongly NP-hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, yield good lower bounds, and generate near-optimal feasible integer solutions for problem instances with many machines and a realistically large number of jobs.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B05 | Inventory, storage, reservoirs |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
work-in-process inventory costs; column generation; Dantzig-Wolfe reformulation; Lagrangian relaxationReferences:
| [1] | Baker, Sequencing with earliness and tardiness penalties: A review, Oper Res 38 (1) pp 22– (1990) · Zbl 0699.90052 |
| [2] | Barnhart, Branch-and-price: Column generation for solving huge integer programs, Oper Res 46 (3) pp 316– (1998) |
| [3] | K. Bülbül P. Kaminsky C. Yano Preemption in single machine earliness/tardiness scheduling Department of IEOR, University of California at Berkeley 2001 |
| [4] | Cattrysse, A dual ascent and column generation heuristic for the discrete lotsizing and scheduling problem with setup times, Management Sci 39 (4) pp 477– (1993) · Zbl 0774.90059 |
| [5] | Chang, Scheduling flexible flow shops with no setup effects, IEEE Trans Robotics Automat 10 (2) pp 112– (1994) · doi:10.1109/70.282536 |
| [6] | H. Chen P. Luh An alternative framework to Lagrangian relaxation approach for job shop scheduling 1999 913 918 |
| [7] | Chen, Parallel machine scheduling with a common due window, European J Oper Res 136 (3) pp 512– (2002) · Zbl 1007.90024 · doi:10.1016/S0377-2217(01)00068-6 |
| [8] | Chen, A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem, European J Oper Res 116 (1) pp 220– (1999) · Zbl 1009.90040 · doi:10.1016/S0377-2217(98)00136-2 |
| [9] | Chen, Solving parallel machine scheduling problems by column generation, INFORMS J Comput 11 (1) pp 78– (1999) · Zbl 1034.90506 |
| [10] | Dixon, Heuristic procedures for multi-item inventory planning with limited storage, IIE Trans 22 (2) pp 112– (1990) |
| [11] | Drexl, Optimization guided lower and upper bounds for the resource investment problem, J Oper Res Soc 52 (3) pp 340– (2001) · Zbl 1131.90378 · doi:10.1057/palgrave.jors.2601099 |
| [12] | Dyer, Formulating the single machine sequencing problem with release dates as a mixed integer program, Discrete Appl Math 26 (2-3) pp 255– (1990) · Zbl 0694.90060 · doi:10.1016/0166-218X(90)90104-K |
| [13] | Eilon, Due dates in job shop scheduling, Int J Prod Res 14 (2) pp 223– (1976) |
| [14] | Farley, A note on bounding a class of linear programming problems, including cutting stock problems, Oper Res 38 (5) pp 922– (1990) · Zbl 0723.90052 |
| [15] | Federgruen, Heuristics for multimachine scheduling problems with earliness and tardiness costs, Management Sci 42 (11) pp 1544– (1996) · Zbl 0879.90115 |
| [16] | Fisher, Optimal solution of scheduling problems using Lagrange multipliers. I, Oper Res 21 (5) pp 1114– (1971) |
| [17] | M. Goemans M. Queyranne A. Schulz M. Skutella Y. Wang Single machine scheduling with release dates 1999 · Zbl 1009.90096 |
| [18] | Graham, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann Discrete Math 5 pp 287– (1979) · Zbl 0411.90044 |
| [19] | Hall, Generating experimental data for computational testing with machine scheduling applications, Oper Res 49 (6) pp 854– (2001) · Zbl 1163.90490 · doi:10.1287/opre.49.6.854.10014 |
| [20] | Hoogeveen, Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems, Math Program 70 pp 173– (1995) · Zbl 0844.90070 · doi:10.1007/BF01585935 |
| [21] | Kanet, Scheduling with inserted idle time: Problem taxonomy and literature review, Oper Res 48 (1) pp 99– (2000) · doi:10.1287/opre.48.1.99.12447 |
| [22] | Kaskavelis, Efficient Lagrangian relaxation algorithms for industry size job-shop scheduling problems, IIE Trans 30 (11) pp 1085– (1998) · doi:10.1080/07408179808966565 |
| [23] | Kubiak, Equivalence of mean flow time problems and mean absolute deviation problems, Oper Res Lett 9 (6) pp 371– (1990) · Zbl 0825.90553 · doi:10.1016/0167-6377(90)90056-B |
| [24] | Lasdon, Optimization theory for large systems (1970) |
| [25] | Lee, Scheduling jobs and maintenance activities on parallel machines, Naval Res Logist 47 (2) pp 145– (2000) · Zbl 0973.90034 |
| [26] | Lenstra, Complexity of machine scheduling problems, Ann Discrete Math 1 pp 343– (1977) · Zbl 0353.68067 |
| [27] | Park, A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints, European J Oper Res 123 (3) pp 504– (2000) · Zbl 0979.90056 · doi:10.1016/S0377-2217(99)00108-3 |
| [28] | Pinedo, A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop, Naval Res Logist 46 (1) pp 1– (1999) · Zbl 0922.90088 |
| [29] | Potts, A decomposition algorithm for the single machine total tardiness problem, Oper Res Lett 1 (5) pp 177– (1982) · Zbl 0508.90045 · doi:10.1016/0167-6377(82)90035-9 |
| [30] | Queyranne, Polyhedral approaches to machine scheduling (1994) |
| [31] | Sarper, Minimizing the sum of absolute deviations about a common due date for the two-machine flow shop problem, Appl Math Model 19 (3) pp 153– (1995) · Zbl 0829.90075 · doi:10.1016/0307-904X(94)00022-X |
| [32] | Savelsbergh, DRIVE: Dynamic routing of independent vehicles, Oper Res 46 (4) pp 474– (1998) · Zbl 0987.90511 |
| [33] | Schulz, Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria pp 416– (1997) |
| [34] | Sousa, A time indexed formulation of non-preemptive single machine scheduling problems, Math Program 54 pp 353– (1992) · Zbl 0768.90041 |
| [35] | Sundararaghavan, Minimizing the sum of absolute lateness in single-machine and multimachine scheduling, Naval Res Logist Quart 31 (2) pp 325– (1984) · Zbl 0544.90052 |
| [36] | Sung, Scheduling in a two-machine flowshop with batch processing machine(s) for earliness/tardiness measure under a common due date, European J Oper Res 131 (1) pp 95– (2001) · Zbl 0979.90029 · doi:10.1016/S0377-2217(99)00447-6 |
| [37] | Van den Akker, Parallel machine scheduling by column generation, Oper Res 47 (6) pp 862– (1999) · Zbl 0979.90051 |
| [38] | Van den Akker, Time-indexed formulations for machine scheduling problems: Column generation, INFORMS J Comput 12 (2) pp 111– (2000) · Zbl 1034.90004 · doi:10.1287/ijoc.12.2.111.11896 |
| [39] | Van den Akker, A polyhedral approach to single-machine scheduling problems, Math Program 85 (3) pp 541– (1999) · Zbl 1072.90523 · doi:10.1007/s101070050071 |
| [40] | Van den Akker, Combining column generation and Lagrangian relaxation to solve a single-machine common due date problem, INFORMS J Comput 14 (1) pp 37– (2002) · Zbl 1238.90096 · doi:10.1287/ijoc.14.1.37.7706 |
| [41] | Vanderbeck, An exact algorithm for IP column generation, Oper Res Lett 19 (4) pp 151– (1996) · Zbl 0873.90074 · doi:10.1016/0167-6377(96)00033-8 |
| [42] | van de Velde, Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation, Ann Oper Res 26 (1-4) pp 257– (1990) · Zbl 0709.90060 |
| [43] | Wolsey, Integer programming (1998) |
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.
