A robust single-machine scheduling problem with scenario-dependent processing times and release dates

Abstract: Many uncertainties arise during the manufacturing process, such as changes in the working environment, traffic transportation delays, machine breakdowns, and worker performance instabilities. These factors can cause job processing times and ready times to change. In this study, we address a scheduling model for a single machine where both job release dates and processing times are scenario dependent. The objective is to minimize the total completion time across the worst-case scenarios. Even without the uncertainty factor, this problem is NP-hard. To solve it, we derive several properties and a lower bound used in a branch-and-bound method to find an optimal solution. We propose nine heuristics based on a linear combination of scenario-dependent processing times and release times for approximate solutions. Additionally, we offer an iterated greedy population-based algorithm that efficiently solves this problem by taking advantage of the diversity of solutions. We evaluate the performance of the proposed nine heuristics and the iterated greedy population-based algorithm.

How to cite this paper

 Wu, C., Chen, J., Lin, W., Zhang, X., Ren, T., Wu, Z & Chung, Y. (2025). A robust single-machine scheduling problem with scenario-dependent processing times and release dates.International Journal of Industrial Engineering Computations , 16(1), 37-50.

Refrences

Aissi, H., Aloulou, M.A., & Kovalyov, M. Y. (2011). Minimizing the number of late jobs on a single machine under due date uncertainty, Journal of Scheduling, 14(4), 351-360.
Alon, N., Azar, N.Y., Weginger, G.J., & Yadid, T. (1998). Approximation schemes for scheduling on parallel machines, Journal of scheduling, 1, 55-66.
Aloulou, M.A., & Della Croce, F. (2008). Complexity of single machine scheduling problems under scenario-based uncertainty, Operations Research Letters, 36(3), 338-342.
Bouamama, S., Blum, C., & Boukerram, A. (2012). A population-based iterated greedy algorithm for the minimum weight vertex cover problem. Applied Soft Computing, 12(6), 1632-1639.
Chekuri, C., Motwani, R., Natarajan, B., & Stein, C. (1997). Approximation Techniques for average completion time scheduling, Proceedings of the annual ACM-SIAM symposium on discrete algorithm (SODA), pp 609-617.
Chen, B., Potts, C.N., & Weginger, J.G. (1998). A review of machine scheduling, complexity and approximability, Handbook of combinatorial optimization, D-Z Du and P. Paradalos (eds.), pp 21-169, Kluwer Academic Press, Boston.
Cheng, S.-R., Yin, Y., Wen, C.-H., Lin, W.-C., & Wu, C.-C. (2017). A two-machine flowshop scheduling problem with precedence constraint on two jobs. Soft Computing, 21(8), 2091-2103.
Dessouky, M.M. (1998). Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maxmun total lateness, Computer & Industrial Engineering, 34(4), 793-806.
de Farias, I. R., Zhao, H., & Zhao, M. (2010). A family of inequalities valid for the robust single machine scheduling polyhedron. Computers and Operations Research, 37(9), 1610-1614.
French, S. (1982). Sequencing and Scheduling, An Introduction to the Mathematics of the Job Shop. Ellis Horwood Limited.
Gilenson, M., Naseraldin, H., & Yedidsion, L. (2018). An approximation scheme for the bi-scenario sum of completion times trade-off problem, Journal of Scheduling, 22(3), 289-304.
Gilenson, M., & Shabtay, D. (2021). Multi-scenario scheduling to maximise the weighted number of just-in-time jobs. Journal of the Operational Research Society, 72(8), 1762-1779.
Hardy, G.H., Littlewood, J. E., & Polya, G. (1967). Inequalities (p. 261). London, Cambridge University Press.
Hermelin, D., Manoussakis, G., Pinedo, M., Shabtay, D., & Yedidsion, L. (2020). Parameterized multi-scenario single-machine scheduling problems, Algorithmica, 82, 2644-2667.
Hochbaum, D.S., & Shmoys, D.B. (1987). Using dual approximation algorithms for scheduling problems, theoretical and practical results, Journal of the ACM, 34, 144-162.
Hollander, M. D., Wolfe, A., & Chicken, E. (2014). Nonparametric Statistical Methods, third edition, John Wiley & Sons, Inc., Hoboken, New Jersey.
Johnson, D. (2001). A theoretician's guide to the experimental analysis of algorithms. Conference, Data Structures, Near Neighbor Searches, and Methodology, Fifth and Sixth DIMACS Implementation Challenges.
Kasperski, A., & Zieliński, P. (2016). Robust discrete optimization under discrete and interval uncertainty, A survey. In Robustness analysis in decision aiding, optimization, and analytics (pp.113-143), Springer, Cham.
Kouvelis, P., & Yu, G. (1996). Robust Discrete Optimization and It Application (Vol.14). Springer Science & Business Media.
Kouvelis, P., Daniels, R. L., & Vairaktarakis, G. (2000). Robust scheduling of a two-machine flow shop with uncertain processing times. Iie Transactions, 32(5), 421-432.
Lenstra, J.K., Rinnooy Kan, A.H.G., & Brucker, P. (1977). Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362.
Lin, W.-C., Xu, J., Bai, D., Chung, I-H., Liu, S.-C., & Wu, C.-C (2019). Artificial bee colony algorithms for the order scheduling with release dates, Soft Computing, 23(18), 8677-8688.
Lin, B.M.T., & Wu, J.M. (2006). Bicriteria scheduling in a two-machine permutation flowshop. International journal of production research, 44(12), 2299-2312
Mastrolilli, M., Mutsanas, N., & Svensson, O. (2013). Single machine scheduling with scenarios. Theoretical Computer Science, 477, 57-66.
Nawaz, M., Enscore Jr, E.E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11(1), 91-95.
Pinedo, M. (2008). Scheduling, theory, algorithms and systems. NJ, Prentice-Hall, Upper Saddle River. Third version.
Reever, C. (1995). Heuristics for scheduling a single machine subject to unequal job release times, European Journal of Operational Research, 80, 397-403.
Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177(3), 2033-2049.
Ruiz, R., & Stützle, T. (2008). An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, European Journal of Operational Research, 187(3),1143-1159.
Schuurman, P., & Woeginger, G.J. (1999). Polynomial time approximation algorithms for machine scheduling, ten open problems, Journal of scheduling, 2, 203-214.
Sevastianov, S.V., & Woeginger, G.J. (1998). Makespan minimization in open shops, a polynomial time approximation scheme, Mathematical Programming, 82, 191-198.
Smith, W.E. (1956). Various optimizers for single stage production, Naval Research Logistics Quarterly, 3(1), 56-66.
Sotskov, I. N., & Werner, F. (2014). Sequencing and scheduling with inaccurate data. Hauppauge, NY, Nova Science Publishers.
Wang, J. B., Lv, D. Y., Wang, S. Y., & Jiang, C. (2023). Resource allocation scheduling with deteriorating jobs and position-dependent workloads. Journal of Industrial and Management Optimization, 19(3), 1658-1669.
Wang, F., & Wu, B. (2024). The k-Sombor Index of Trees. Asia-Pacific Journal of Operational Research, 41(1). DOI, 10.1142/S0217595923500264.
Wu, C.-C., Wu, W.-H., Chen, J.-C., Yin, Y., & Wu, W.-H. (2013). A study of the single-machine two-agent scheduling problem with release times, Applied Soft Computing, 13, 998-1006.
Wu, C.-C., Gupta, J.N.D., Cheng, S.R., Lin, B.M.T., Yip, S.H., & Lin, W.C. (2021). Robust scheduling of a two-stage assembly shop with scenario-dependent processing times. International Journal of Production Research, 59(17), 5372-5387.
Yang, J., & Yu, G. (2002). On the robust single machine scheduling problem, Journal of Combinatorial Optimization, 6(1), 17-33.
Yin, Y., Wu, W.-H., Cheng, S.-R., & Wu C.-C. (2012). An investigation on a two-agent single-machine scheduling problem with unequal release dates. Computers & Operations Research, 39, 3062-3073.