Order scheduling with controllable processing times, common due date and the processing deadline

Abstract

Due date quotation and scheduling are important tools to match demand with production capacity in the MTO (make-to-order) environment. We consider an order scheduling problem faced by a manufacturing firm operating in an MTO environment, where the firm needs to quote a common due date for the customers, and simultaneously control the processing times of customer orders (by allocating extra resources to process the orders) so as to complete the orders before a given deadline. The objective is to minimize the total costs of earliness, tardiness, due date assignment and extra resource consumption. We show the problem is NP-hard, even if the cost weights for controlling the order processing times are identical. We identify several polynomially solvable cases of the problem, and develop a branch and bound algorithm and three Tabu search algorithms to solve the general problem. We then conduct computational experiments to evaluate the performance of the three Tabu-search algorithms and show that they are generally effective in terms of solution quality.

Keywords

Order scheduling / due date assignment / controllable processing times / deadline

References

[1] Baker K., Scudder G.. Sequencing with earliness and tardiness penalties: a review. Operations Research, 1990, 38(1): 22-36.

[2] Beicourt M.. Outsourcing - the benefits and risks. Human Resource Management Review, 2006, 16(2): 269-279.

[3] Biskup D., Jahnke H.. Common due date assignment for scheduling on a single machine with jointly reducible processing times. International Journal of Production Economics, 2001, 69(3): 317-322.

[4] Cheng T.C.E., Shakhlevich N.V.. Two machine open shop problem with controllable processing times. Discrete Optimization, 2007, 4(1): 175-184.

[5] Cheng T.C.E., Ding Q., Lin B.M.T.. A concise survey on the scheduling problems with deteriorating processing times. European Journal Operational Research, 2004, 152(1): 1-13.

[6] Cheng T.C.E., Oğaz C., Qi X.D.. Due-date assignment and single machine scheduling with compressible processing times. International Journal of Production Economics, 1996, 43(1-2): 29-35.

[7] Choi B.-C., Leung J.-T., Pinedo M.L.. Complexity of a scheduling problem with controllable processing times. Operations Research Letters, 2010, 38(2): 123-126.

[8] Della C.F., Narayan V., Tadei R.. The two-machine total completion time flow shop problem. European Journal of Operational Research, 1996, 90(2): 227-237.

[9] Garey M.R., Johnson D.S.. Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, San Francisco: Freeman.

[10] Gordon V., Proth J.M., Chu C.B.. Due date assignment and scheduling: SLK, TWK and other due date assignment models. Production Planning & Control, 2002, 13(2): 117-132.

[11] Gordon V., Proth J. M., Chu C.B.. A survey of the state-of-the-art of common due date assignment and scheduling research. European Journal of Operational Research, 2002, 139(1): 1-25.

[12] Gordon V.S., Strusevich V. A.. Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment. Computers & Operations Research, 1999, 26(2): 157-177.

[13] Gunasekaran A., Ngai E.W.T.. Build-to-order supply chain management: a literature review and framework for development. Journal of Operations Management, 2005, 23(5): 423-451.

[14] Hall N.G., Posner M.E.. Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date. Operations Research, 1991, 39(5): 836-846.

[15] Hall N.G., Kubiak W., Sethi S.P.. Earliness-tardiness scheduling problems, II: deviation of completion times about a restrictive common due date. Operations Research, 1991, 39(5): 847-856.

[16] Hardy G.H., Littlewood J.E., Polya G.. Inequalities, 1934, NY: Cambridge University Press.

[17] He Y., Qi W., Cheng T.C.. Single-machine scheduling with trade-off between number of tardy jobs and compression cost. Journal of Scheduling, 2007, 10(5): 303-310.

[18] Huynh T.N., Ameur S.. Due dates assignment and JIT scheduling with equal size jobs. European Journal of Operational Research, 2010, 205(2): 280-289.

[19] Janiak A.. Minimization of resource consumption under a given deadline in the two-processor flow-shop scheduling problem. Information Processing Letters, 1989, 32(3): 101-112.

[20] Jansen K., Mastrolilli M., Solis-Oba R.. Approximation schemes for job shop scheduling problems with controllable processing times. European Journal of Operational Research, 2005, 167(2): 297-319.

[21] Kaminsky P., Lee Z.H.. On-line algorithms for flow shop due date quotation., 2002, University of California: Berkeley

[22] Kaminsky P., Lee Z.H.. Effective on-line algorithms for reliable due date quotation and-large-scale scheduling. Journal of Scheduling, 2008, 11(3): 187-204.

[23] Kaspi M., Shabtay D.. Convex resource allocation for minimizing the makespan in a single machine with job release dates. Computers & Operations Research, 2004, 31(9): 1481-1489.

[24] Lawler E.L., Wood D.E.. Branch-and-bound methods: a survey. Operations Research, 1966, 14(4): 699-719.

[25] Leyvand Y., Shabtay D., Steiner G.. Optimal delivery time quotation to minimize total tardiness penalties with controllable processing times. IIE Transactions, 2010, 42(3): 221-231.

[26] Mitten L. G.. Branch-and-bound methods: general formulation and properties. Operations Research, 1970, 18(1): 24-34.

[27] Monma C.L., Schrijver A., Todd M. J., Wei V. K.. Convex resource allocation problems on directed acyclic graphs: duality, complexity, special cases and extensions. Mathematics of Operations Research, 1990, 15(4): 736-748.

[28] Ng C.T.D., Cheng T.C.E., Kovalyov M.Y., Lam S. S.. Single machine scheduling with a variable common due date and resource-dependent processing times. Computers & Operations Research, 2003, 30(8): 1173-1185.

[29] Nowicki E., Zdrzalka S.. A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times. Discrete Applied Mathematics, 1995, 63(3): 237-256.

[30] Panwalkar S.S., Smith M.L., Seidmann A.. Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research, 1982, 30(2): 391-399.

[31] Pinedo M.. Scheduling: Theory, Algorithms and Systems, 2012, Springer: Berlin.

[32] Qi X., Tu F.-S.. Scheduling a single machine to minimize earliness penalties subject to the SLK due-date determination method. European Journal of Operations Research, 1998, 105(3): 502-508.

[33] Shabtay D., Steiner G.. Two due date assignment problems in scheduling a single machine. Operations Research Letters, 2006, 34(6): 683-691.

[34] Shabtay D., Steiner G.. A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 2007, 155(13): 1643-1666.

[35] Shabtay D., Steiner G.. Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine. Manufacturing & Service Operations Management, 2007, 9(3): 332-350.

[36] Shabtay D., Steiner G.. The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times. Annals of Operation Research, 2008, 159(1): 25-40.

[37] Shabtay D., Kaspi M.. Parallel machine scheduling with a convex resource consumption function. European Journal of Operational Research, 2006, 173(1): 92-107.

[38] Slotnick S.A., Sobel M.J.. Manufacturing lead-time rules: customer retention versus tardiness costs. European Journal of Operational Research, 2005, 163(3): 825-856.

[39] Spearman M.L., Zhang R.Q.. Optimal lead time policies. Management Science, 1999, 45(2): 290-295.

[40] Tseng C.T., Liao C.J., Huang K.L.. Minimizing total tardiness on a single machine with controllable processing times. Computers & Operations Research, 2009, 36(6): 1852-1858.

[41] Wan G.H., Yen B.P.C., Li C.-L.. Single machine scheduling to minimize total processing plus weighted flow cost is NP-hard. Information Processing Letters, 2001, 79(6): 273-280.

[42] Xu K.L., Feng Z.R., Ke L.J.. Single machine scheduling with total tardiness criterion and convex controllable processing times. Annals of Operations Research, 2011, 186(1): 383-391.

[43] Yedidsion Y., Shabtay D., Kaspi M.. Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling. Discrete Applied Mathematics, 2011, 159(12): 1264-1278.