Scheduling stochastic jobs on a single machine to minimize weighted number of tardy jobs
Keywords:
Number of tardy jobs, scheduling, single machine, stochastic.Abstract
ABSTRACT
An important scheduling problem in manufacturing and service organizations is the on-time deliveries of products and services. This paper addresses a single machine scheduling problem wherein processing times and/or due-dates are random variables and fixed weights (penalties) are imposed on late jobs. The objective is to find the schedule that minimizes the expected weighted number of tardy jobs. The problem is NP-hard; however, we study the three resulting scenarios: the scenario with stochastic processing times and stochastic due-dates, the scenario with deterministic processing times and stochastic due-dates, and the scenario with stochastic processing times and deterministic due-dates. We prove that special cases of these scenarios are solvable optimally in polynomial time, and introduce heuristic methods for their general cases. Our computational results show that the proposed heuristics perform well in producing the optimal or near optimal solutions. The illustrative examples and computational results also demonstrate that the stochasticity of processing times and/or due-dates can affect scheduling decisions.
References
REFERENCES
Aldowaisan, T. A. & Allahverdi, A. 2012. No-wait flowshop scheduling problem to minimize the number of tardy jobs. International Journal of Advance Manufacturing Technology 61(1): 311–323.
Aydilek, H. & Allahverdi, A. 2010. Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time. Computers & Mathematics with Applications 59(2): 684-693.
Baker, K. R. & Trietsch, D. 2009a. Principles of Sequencing and Scheduling. John Wiley:
New Jersey, USA.
Baker, K. R. & Trietsch, D. 2009b. Safe scheduling: Setting due dates in single-machine problems. European Journal of Operational Research 196(1): 69-77.
Balut, S. J. 1973. Scheduling to minimize the number of late jobs when set-up and processing times are uncertain. Management Science 19(11): 1283-1288.
Baptiste, P. 1999. Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. Journal of Scheduling 2(6): 245-252.
Boxma, O. J. & Forst, F. G. 1986. Minimizing the expected weighted number of tardy jobs in stochastic flow shops. Operations Research Letters 5(3): 119-126.
Cai, X. & Zhou, X. 2005. Single machine scheduling with exponential processing times and general stochastic cost functions. Journal of Global Optimization 31(2): 317-332.
Chiang, T. C. & Fu, L. C. 2009. Using a family of critical ratio-based approaches to minimize the number of tardy jobs in the job shop with sequence dependent setup times. European Journal of Operational Research 196(1): 78–92.
De, P., Ghosh, J. B. & Wells, C. E. 1991. On the minimization of the weighted number of
tardy jobs with random processing times and deadline. Computers & Operations Research 18(5): 457–463.
Desprez, C., Chu, F. & Chu, C. 2009. Minimising the weighted number of tardy jobs in a
hybrid flow shop with genetic algorithm. International Journal of Computer Integrated Manufacturing 22(8): 745–757.
Dhouib, E. Teghem, J. & Loukil, T. 2013. Minimizing the number of tardy jobs in a permutation flowshop scheduling problem with setup times and time lags constraints. Journal of Mathematical Modelling and Algorithms, doi 10.1007/s10852-012-9180-x.
Elyasi, A. & Salmasi N. 2013a. Stochastic scheduling with minimizing the number of tardy jobs using chance constrained programming. Mathematical and Computer Modelling 57(5-6): 1154-1164.
Elyasi, A. & Salmasi, N. 2013b. Stochastic flow-shop scheduling with minimizing the expected number of tardy jobs. International Journal of Advanced Manufacturing Technology, doi 10-1007/s00170-012-4328-4.
Erel, E. & Ghosh, J. B. 2007. Batch scheduling to minimize the weighted number of tardy jobs. Computers & Industrial Engineering 53(3): 394–400.
Erenay, F. S., Sabuncuoglu, I. Toptal, A. & Tiwari, M. K. 2010.
Graham, R. L., Lawler, E. L., Lenstra, J. K. & Rinnooy Kan, A. H. G. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5: 287–326.
Hoogeveen, H. & T’kindt, V. 2012. Minimizing the number of late jobs when the start time of the machine is variable. Operations Research Letters 40(5): 353-355.
Horowitz, E. & Sahni, S. 1983. Fundamentals of Data Structures. Computer Science Press: Rockville, USA.
Jafari, A. & Moslehi, G. 2012. Scheduling linear deteriorating jobs to minimize the number
of tardy jobs. Journal of Global Optimization 54(2): 389–404.
Jang, W. & Klein, C. M. 2002. Minimizing the expected number of tardy jobs when processing times are normally distributed. Operations Research Letters 30(2): 100-106.
Jolai, F. , Rabbani, M., Amalnick, S., Dabaghi, A., Dehghan, M. & Parast, M. Y. 2007. Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs. Applied Mathematics and Computation 194(2): 552-560.
Karp, R. M. 1972. Reducibility among combinatorial problems. In: Millerm R.E. and Thatcher, J.W. (Eds.). Complexity of Computer Computations. Pp 85-103. Plenum Press: New York.
Lee, W. C., Lin, J. B. & Shiau, Y. R. 2011. Deteriorating job scheduling to minimize the number of late jobs with setup times. Computers & Industrial Engineering 61(3): 782–787.
Lee, J. Y. & Kim, Y. D. 2012. Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance. Computers & Operations Research 39(9): 2196–2205.
Li, W. & Alfa, A. S. 2005. Scheduling stochastic jobs on a repairable machine with general phase type uptime. Mathematical Methods of Operations Research 61(3): 399-417.
Molaee, E., Moslehi, G. & Reisi, M. 2011. Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem with availability constraint. Computers and Mathematics with Applications 62(9): 3622-3641.
Moore, J. M. 1968. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science 15(1): 102-109.
Mosheiov, G. & Oron, D. 2012. Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times. Computers & Operations Research 39(7): 1601-1604.
Mosheiov, G. & Sarig, A. 2010. Minimum weighted number of tardy jobs on an m-machine flow-shop with a critical machine. European Journal of Operational Research 201(2): 404-
Panwalkar, S. S. & Koulamas, C. 2012. An O(n2) algorithm for the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines.
European Journal of Operational Research 221(1): 7-13.
Pinedo, M. L. 1983. Stochastic scheduling with release dates and due dates. Operations Research 31(3): 559-572.
Rasti-Barzoki, M., Hejazi, S. R. & Mazdeh, M. M. 2013. A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs. Applied Mathematical Modelling 37(7): 4924-4937.
Reisi, M. & Moslehi, G. 2011. Minimizing the number of tardy jobs and maximum earliness in the single machine scheduling using an artificial immune system. International Journal of Advanced Manufacturing Technology 54(5-8): 749-756.
Ruiz, R. & Allahverdi, A. 2009. Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness. Computers & Operations Research 36(4): 1268-1283.
Sadykov, R. A. 2008. Branch-and-check algorithm for minimizing the weighted number of
late jobs on a single machine with release dates. European Journal of Operational Research 189(3): 1284–1304.
Sarin, S. C., Erel, E. & Steiner, G. 1991. Sequencing jobs on a single machine with a common due date and stochastic processing times. European Journal of Operational research 51(2): 188-198.
Seo, D. K., Klein, C. M. & Jang, W. 2005. Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models. Computers & Industrial Engineering 48(2): 153-161.
Soroush, H. M. 1999. Optimal sequencing and due-date determination in a stochastic single
machine system with earliness and tardiness costs. European Journal of Operational Research 113(2): 450-468.
Soroush, H. M. 2006. Single machine scheduling with stochastic processing times or stochastic due-dates to minimizing the number of early and tardy jobs. International Journal of Operations Research 3(2): 90-108.
Soroush, H. M. 2007. Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem. European Journal of Operational Research 181(1): 266-277.
Soroush, H. M., 2010. Solving a stochastic single machine problem with initial idle time and quadratic objective. Computers & Operations Research 37(7): 1328–1347.
Soroush, H. M. & Allahverdi, A. 2005. Stochastic two-machine flowshop scheduling problem with total completion time criterion. International Journal of Industrial Engineering: theory applications, and practice 12(2): 157-170.
Steiner, G. & Zhang, Z. 2011. Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries. Annals of Operations Research 191(1):
–181.
Tang, H. Y., Tang, C. H. & Zhao, C. L. 2010. A preemptive-resume stochastic scheduling model with disruption. System Engineering Theory and Practice 30(4): 751-757.
Trietsch, D. & Baker, K. R. 2008. Minimizing the number of tardy jobs with stochastically-ordered processing times. Journal of Scheduling 11(1): 71-73.
Umble, M. M. and Srikanth, M. L. 1995. Synchronous manufacturing: Principles for world-class excellence. Spectrum Publication Company: Wallingford, USA.
Varmazyar, M. & Salmasi, N. 2012. Sequence-dependent flow shop scheduling problem minimizing the number of tardy jobs. International Journal of Production Research 50(20): 5843-5858.
Wan, G. & Yen, B. P. C. 2009. Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs. European Journal of Operational Research 195(1): 89–97.
Zhang, Q., Manier, H. & Manier, M. A. 2012. A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times. Computers & Operations Research 39(7): 1713-1723.
