Minimizing job shop inventory with on-time delivery guarantees

Abstract

In this paper, we introduce a new job shop model that minimizes a well-motivated inventory measure while assuring on-time job deliveries. For this new problem, we introduce precise notation and formalization. A decomposition scheme is discussed in detail, which is subsequently utilized in a new shifting bottleneck procedure (SBP) for the problem. In addition to SBP, we propose another heuristic method based on successive insertion of operations. Algorithms are fine tuned through experimentation. Moreover, the two heuristic procedures are compared in terms of computation time and solution quality, using disguised actual factory data.

Keywords

Job shop / inventory models / deadlines / heuristics

References

[1] Adams J., Balas E., Zawack D.. The shifting bottleneck procedure for job shop scheduling. Management Sci., 1988, 34(3): 391-401.

[2] Ahmadi R.H., Bagchi U.. Just-in-time scheduling in single machine systems, 1986, Austin, TX: Department of Management, University of Texas

[3] Ahmadi R.H., Bagchi U.. Minimizing job idleness in deadline constrained environments. Oper. Res., 1992, 40: 972-985.

[4] Baker K.R.. Introduction to Sequencing and Scheduling, 1974, NY: Wiley

[5] Balas E., Lancia G., Vazacopoulos A.. On the facial structure of scheduling polyhedra. J. Combinatorial Optimization, 1998, 1(4): 329-353.

[6] Balas E., Lenstra J.K., Vazacopoulos A.. The one-machine problem with delayed precedence constraints and its use in job shop scheduling. Management Sci., 1995, 41(1): 94-109.

[7] Balas E., Vazacopoulos A.. Guided local search with shifting bottleneck for job-shop scheduling. Management Sci., 1998, 44: 262-275.

[8] Belouadah H., Posner M.E., Potts C.N.. Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Appl. Math., 1992, 36: 213-231.

[9] Carlier J., Pinson E.. Adjustments of heads and tails for the job-shop problem. European J. Oper. Res., 1994, 78: 146-161.

[10] Chand S., Schneeberger H.. Single machine scheduling to minimize weighted earliness subject to no tardy jobs. European J. Oper. Res., 1988, 34: 221-230.

[11] Chekuri C., Motwani R., Natarajan B., Stein C.. Approximation techniques for average completion time scheduling. SIAM J. Comput., 2001, 31: 146-166.

[12] Chu C.. A branch-and-bound algorithm to minimize total flow time with unequal release dates. Naval Res. Logist., 1992, 39: 859-875.

[13] Della Croce F., Ghirardi M., Tadei R.. An improved branch-and-bound algorithm for the two machine total completion time flow shop problem. European J. Oper. Res., 2002, 139: 293-301.

[14] Du J., Leung J.Y.. Minimizing mean flow time with release time and deadline constraints. J. Algorithms, 1993, 14: 45-68.

[15] Gélinas S., Soumis F.. A dynamic programming algorithm for single machine scheduling with ready times. Ann. Oper. Res., 1997, 69: 135-156.

[16] Goemans M.X.. Improved approximation algorithms for scheduling with release dates. Proc. 8th ACM-SIAM Symposium on Discrete Algorithms, 1997, 25: 591-598.

[17] Hariri A.M.A., Potts C.N.. Algorithm for single machine sequencing with release dates to minimize total weighted completion time. Discrete Appl. Math., 1983, 5: 99-109.

[18] Lambrecht M.R., Ivens P.L., Vandaele N.J.. ACLIPS: A capacity and lead time integrated procedure for scheduling. Management Sci., 1998, 44: 1548-1561.

[19] Lawrence S.. Supplement to resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques, 1984, Pittsburgh, PA: GSIA, CarnegieMellon University

[20] Lenstra J.K., Rinnooy Kan A.H.G., Brucker P.. Complexity of machine scheduling problems. Ann. Discrete Math., 1977, 1: 343-362.

[21] Martin, P. and D.B. Shmoys, “A new approach to computing optimal schedules for the job-shop scheduling problem”, in Proc. 5th Internat. IPCO Conf., pp389–403, 1996.

[22] Nowicki E., Smutnicki C.. A fast tabu search algorithm for job shop problem. Management Sci., 1996, 42: 797-813.

[23] Ovacik I.M., Uzsoy R.. Decomposition Methods for Complex Factory Scheduling Problems, 1997, Boston, MA: Kluwer

[24] Pan Y.. An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time. Oper. Res. Lett., 2003, 31(6): 492-496.

[25] Pan Y.. Production scheduling for suppliers in the extended enterprise, 2003, Madison, WI: Department of Industrial Engineering, University of Wisconsin

[26] Posner M.. Minimizing weighted completion times with deadlines. Oper. Res., 1985, 33: 562-574.

[27] Potts C.N., Van Wassenhove L.N.. Algorithm for single machine sequencing with deadlines to minimize total weighted completion time. European J. Oper. Res., 1983, 12: 379-387.

[28] Ptak C.A., Schragenheim E.. ERP: Tools, Techniques, and Applications for Integrating the Supply Chain, 2000, Boca Raton, FL: St. Lucie Press/APICS series on resource management

[29] Roy B., Sussmann B.. Les problèmes d’ordonnancements avec contraintes disjonctives, 1964, Paris: SEMA

[30] Schulz A.S., Skutella M.. Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria, 1996, Berlin, Germany: Fachbereich Mathematik, Technische Universität Berlin

[31] Singer M., Pinedo M.. A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. IIE Trans., 1998, 30: 109-118.

[32] Smith W.E.. Various optimizers for single-stage production. Naval Res. Logist. Quart., 1956, 3: 59-66.

[33] Tkindt V., Gupta J.N.D., Billaut J.-C.. Two-machine flowshop scheduling with a secondary criterion. Computers & Oper. Res., 2003, 30(4): 505-526.

[34] Vaessens R.J.M., Aarts E.H.L., Lenstra J.K.. Job shop scheduling by local search. INFORMS J. Comput., 1996, 8: 302-317.

[35] Van de Velde S.L.. Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation. Ann. Oper. Res., 1990, 26: 257-268.

[36] Werner F., Winkler A.. Insertion techniques for the heuristic solution of the job shop problem. Discrete Applied Math., 1995, 58: 191-211.

[37] Womack J.P., Jones D.T., Roos D.. Lean Thinking: Banish Waste and Create Wealth in Your Corporation, 1996, New York, NY: Simon & Schuster