Integrated Due Date Setting and Scheduling on a Single Machine Considering an Unexpected Unavailability

Subject Areas : Operation and Chain Management

Mehdi Iranpoor ¹ , Seyed Mohammad Taghi Fatemi Ghomi ²

1 - Department of Industrial and Systems Engineering, Isfahan University of Technology,Isfahan, Iran
2 - Department of Industrial Engineering, Amirkabir University of Technology, Tehran, Iran.

Received: 2016-07-27 Accepted : 2017-11-20 Published : 2019-03-01

Keywords: Lower bound, Duedate setting, Unexpected unavailability, Machine scheduling, Iterated dynasearch,

Abstract :

In this paper, an integrated machine scheduling withits due date setting problem has been considered. It is assumed that the machine is subject to some kind of random unavailability. Due dates should be set in an attractive and reliable manner, implying that they should be short and possible to be met. To this end, first, long due dates are penalized in the objective function. Then, for each customer order, the probability of meeting his/her promised due dateis forced to be at least as large as his/her required service level. To handle this integrated problem, first, the optimal due date formulafor any arbitrary sequence is derived. By using this formula, the mathematical programming formulation of the problem,including a nonlinear non-convex expression, is developed. By defining a piecewise linear under-estimator, the solutions of the resultantmixed integer linear programming formulation have become the lower bounds of the problem. Dynasearch is a very efficient heuristic utilizing the dynamic programming approach to search exponential neighborhoods in the polynomial time. Aniterated dynasearch heuristic is developed for the sequencing part of the problem. Each generated sequence is evaluated by computing its optimal due datesusing the above-mentioned formula. Numerical results confirmed the high quality of the solutions found by this algorithm, as compared with the lower bound.

References:

Agnetis, A., Detti, P. & Martineau, P. (2017). Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions. Computers & Operations Research, 79(1), 109–118.

Angel, E.,& Bampis, E. (2005). A multi-start dynasearch algorithm for the time dependent single-machine total weighted tardiness scheduling problem. European Journal of Operational Research, 162(1), 281–289.

Baker, K.R. (2014). Setting optimal due dates in a basic safe-scheduling model. Computers & Operations Research, 41(1), 109–114.

Baker, K.R.,& Trietsch, D. (2015). Trading off due-date tightness and job tardiness in a basic scheduling model. Journal of Scheduling, 18(3), 305-309.

Baker, K.R.,& Trietsch, D. (2009). Safe scheduling: Setting due dates in single-machine problems. European Journal of Operational Research, 196(1), 69–77.

Bergamini, M.L., Grossmann, I., Scenna, N.,& Aguirre, P. (2008). An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms. Computers & Chemical Engineering, 32(3), 477–493.

Congram, R. K., Potts, C.N.,& Velde, S.L.V.D. (2002). An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem. INFORMS Journal on Computing, 14(1), 52-67

Ding, J., Lu, Z., Cheng, T.C.E.,& Xu, L. (2016). Breakout dynasearch for the single-machine total weighted tardiness problem. Computers & Industrial Engineering, 98(1), 1–10.

Dumitrescu, I., &Stutzle, T. (2010). Usage of Exact Algorithms to Enhance Stochastic Local Search Algorithms, In:Matheuristics.Springer, New York.

Elyasi, A.,& Salmasi, N. (2013). Due date assignment in single machine with stochastic processing times. International Journal of Production Research, 51(8), 2352-2362.

Gerstl, E.,& Mosheiov, G. (2013). Minmax due-date assignment with a time window for acceptable lead-times. Annals of Operations Research, 211(1), 167–177.

Grosso, A., Croce, F.D.,& Tadei, R. (2004). An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem. Operations Research Letters, 32(1), 68–72.

Huo, Y., Reznichenko, B.,& Zhao, H. (2014). Minimizing total weighted completion time with an unexpected machine unavailable interval. Journal of Scheduling, 17(2), 161–172.

Kacem, I.,& Kellerer, H. (2016). Semi-online scheduling on a single machine with unexpected breakdown. Theoretical Computer Science, 646(1), 40–48.

Kacem, I., Nagih, A.,& Seifaddini, M. (2014). Maximum lateness minimization with positive tails on a single machine with an unexpected non-availability interval.Computer Applications and Information Systems (WCCAIS), 2014 World Congress on,IEEE Press, 1-5.

Kedad-Sidhoum, S.,& Sourd, F. (2010). Fast neighborhood search for the single machine earliness–tardiness scheduling problem. Computers & Operations Research, 37(8), 1464–1471.

Keskinocak, P., & Tayur, S. (2004). Due date management policies,In: Handbook of Quantitative Supply Chain Analysis.Kluwer Academic Publishers, Boston.

Miller, C.E., Tucker, A.W.,& Zemlin, R.A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 7(4), 326-329.

Montgomery, D.C., & Runger, G.C. (2014). Applied Statistics and Probability for Engineers. 6th edition,Wiley, Danvers.

Mor, B., Mosheiov, G.,& Shabtay, D. (2013). A note: Minmax due-date assignment problem with lead-time cost. Computers & Operations Research, 40(8), 2161–2164.

Öncan, T., Altınel, İ.K.,& Laporte, G. (2009). A comparative analysis of several asymmetric traveling salesman problem formulations. Computers & Operations Research, 36(3), 637–654.

Pinedo, M. L. (2012). Scheduling: theory, algorithms, and systems. 4th edition,Springer Science & Business Media, New York.

Shabtay, D. (2010). Scheduling and due date assignment to minimize earliness, tardiness, holding, due date assignment and batch delivery costs. International Journal of Production Economics, 123(1), 235–242.

Shabtay, D. (2016). Optimal restricted due date assignment in scheduling. European Journal of Operational Research, 252(1), 79–89.

Shabtay, D.,&Steiner, G. (2006). Two due date assignment problems in scheduling a single machine. Operations Research Letters, 34(6), 683–691.

Slotnick, S.A. (2014). Lead-time quotation when customers are sensitive to reputation. International Journal of Production Research, 52(3), 713-726.

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

Sourd, F. (2006). Dynasearch for the earliness–tardiness scheduling problem with release dates and setup constraints. Operations Research Letters, 34(5), 591–598.

Yin, Y., Cheng, T.C.E., Yang, X.,&Wu, C.C. (2015). Two-agent single-machine scheduling with unrestricted due date assignment. Computers & Industrial Engineering, 79, 148–155.

Yin, Y., Wang, D.J., Wu, C.C.,&Cheng, T.C.E. (2016). CON/SLK Due Date Assignment and Scheduling on a Single Machine with Two Agents. Naval Research Logistics, 63(5), 416-429.

Yin, Y., Wang, Y., Cheng, T.C.E.,Liu, W.,&Li, J. (2017). Parallel-machine scheduling of deteriorating jobs with potential machine disruptions. Omega,69(1), 17–28.