×

Single machine scheduling with release dates: a distributionally robust approach. (English) Zbl 07709093

Summary: In the present study, a single machine scheduling problem with job release dates is considered, where the job processing time is depicted by an ambiguity set, with the mean, the mean absolute deviation, and the support set information given. To the best of our knowledge, this is the first time that a distributionally robust optimization method is applied to the single machine scheduling with release dates. Based on the risk attitude of the decision maker, two distributionally robust optimization models are proposed, namely, the risk-neutral and risk-averse scheduling. The two models concern with the worst-case performance and the robust conditional value-at-risk with respect to the total flow time, respectively. Since the proposed robust optimization models are intractable in nature, we reformulate them as two separate mixed-integer linear programming models, which can then be solved via off-the-shelf solvers. Interestingly, it is proved that the mean absolute deviation can be ignored in the risk-neutral robust model. Thus a more succinct reformulation is constructed, which can be rapidly solved to optimum. Furthermore, extensive numerical experiments are performed with the stochastic programming model as a benchmark. And it is observed that the risk-averse model outperforms the others on both the average and worst-case metrics in most cases. Meanwhile, the risk-neutral model is more preferable on the average metric when the jobs are sparsely released.

MSC:

90Bxx Operations research and management science
Full Text: DOI

References:

[1] Al-Khamis, T.; M’Hallah, R., A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity, Computers & Operations Research, 38, 12, 1747-1759 (2011) · Zbl 1215.90030
[2] Alimoradi, S.; Hematian, M.; Moslehi, G., Robust scheduling of parallel machines considering total flow time, Computers & Industrial Engineering, 93, 152-161 (2016)
[3] Bachtler, O.; Krumke, S. O.; Le, H. M., Robust single machine makespan scheduling with release date uncertainty, Operations Research Letters, 48, 6, 816-819 (2020) · Zbl 1525.90184
[4] Basciftci, B.; Ahmed, S.; Shen, S., Distributionally robust facility location problem under decision-dependent stochastic demand, European Journal of Operational Research, 292, 2, 548-561 (2021) · Zbl 1487.90429
[5] Bruni, M. E.; Khodaparasti, S.; Demeulemeester, E., The distributionally robust machine scheduling problem with job selection and sequence-dependent setup times, Computers & Operations Research, 123, 105017 (2020) · Zbl 1458.90263
[6] Castro, P. M.; Harjunkoski, I.; Grossmann, I. E., Discrete and continuous-time formulations for dealing with break periods: Preemptive and non-preemptive scheduling, European Journal of Operational Research, 278, 2, 563-577 (2019) · Zbl 1430.90248
[7] Chang, Z.; Ding, J.-Y.; Song, S., Distributionally robust scheduling on parallel machines under moment uncertainty, European Journal of Operational Research, 272, 3, 832-846 (2019) · Zbl 1403.90382
[8] Chang, Z.; Song, S.; Zhang, Y.; Ding, J.-Y.; Zhang, R.; Chiong, R., Distributionally robust single machine scheduling with risk aversion, European Journal of Operational Research, 256, 1, 261-274 (2017) · Zbl 1394.90266
[9] Chen, R.; Yuan, J.; Ng, C. T.; Cheng, T., Single-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterion, European Journal of Operational Research, 293, 1, 79-92 (2021) · Zbl 1487.90280
[10] Cheng, C.; Adulyasak, Y.; Rousseau, L.-M.; Sim, M., Robust drone delivery with weather information, History (2020)
[11] Chu, C., Efficient heuristics to minimize total flow time with release dates, Operations Research Letters, 12, 5, 321-330 (1992) · Zbl 0769.90047
[12] Daniels, R. L.; Kouvelis, P., Robust scheduling to hedge against processing time uncertainty in single-stage production, Management Science, 41, 2, 363-376 (1995) · Zbl 0832.90050
[13] Davari, M.; Ranjbar, M.; De Causmaecker, P.; Leus, R., Minimizing makespan on a single machine with release dates and inventory constraints, European Journal of Operational Research, 286, 1, 115-128 (2020) · Zbl 1443.90177
[14] de Weerdt, M.; Baart, R.; He, L., Single-machine scheduling with release times, deadlines, setup times, and rejection, European Journal of Operational Research, 291, 2, 629-639 (2021) · Zbl 1487.90288
[15] Delage, E.; Ye, Y. Y., Distributionally robust optimization under moment uncertainty with application to data-driven problems, Operations Research, 58, 3, 595-612 (2010) · Zbl 1228.90064
[16] El Ghaoui, L.; Oustry, F.; Lebret, H., Robust solutions to uncertain semidefinite programs, SIAM Journal on Optimization, 9, 1, 33-52 (1998) · Zbl 0960.93007
[17] Ertem, M.; Ozcelik, F.; Saraç, T., Single machine scheduling problem with stochastic sequence-dependent setup times, International Journal of Production Research, 57, 10, 3273-3289 (2019)
[18] Faigle, U.; Kern, W., On the core of ordered submodular cost games, Mathematical Programming, 3, 483-499 (2000) · Zbl 0980.90103
[19] Goemans, M. X.; Queyranne, M.; Schulz, A. S.; Skutella, M.; Wang, Y., Single machine scheduling with release dates, SIAM Journal on Discrete Mathematics, 15, 2, 165-192 (2002) · Zbl 1009.90096
[20] Elsevier · Zbl 0411.90044
[21] Herr, O.; Goel, A., Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints, European Journal of Operational Research, 248, 1, 123-135 (2016) · Zbl 1346.90351
[22] Jiang, R. W.; Shen, S. Q.; Zhang, Y. L., Integer programming approaches for appointment scheduling with random no-shows and service durations, Operations Research, 65, 6, 1638-1656 (2017) · Zbl 1382.90042
[23] Jiang, R. W.; Shen, S. Q.; Zhang, Y. L., Integer programming approaches for appointment scheduling with random no-shows and service durations, Operations Research, 65, 6, 1638-1656 (2017) · Zbl 1382.90042
[24] Kleywegt, A. J.; Shapiro, A.; Homem-de Mello, T., The sample average approximation method for stochastic discrete optimization, SIAM Journal on Optimization, 12, 2, 479-502 (2002) · Zbl 0991.90090
[25] Elsevier · Zbl 0353.68067
[26] Li, Y.; Kuo, Y.-H.; Li, R.; Shen, H.; Zhang, L., A target-based distributionally robust model for the parallel machine scheduling problem, International Journal of Production Research, 1-22 (2022)
[27] Liu, X.; Chu, F.; Zheng, F.; Chu, C.; Liu, M., Parallel machine scheduling with stochastic release times and processing times, International Journal of Production Research, 1-20 (2020)
[28] Lo, A. W., Semi-parametric upper bounds for option prices and expected payoffs, Journal of Financial Economics, 19, 2, 373-387 (1987)
[29] Lu, C. C.; Lin, S. W.; Ying, K. C., Robust scheduling on a single machine to minimize total flow time, Computers & Operations Research, 39, 7, 1682-1691 (2012) · Zbl 1251.90167
[30] Lu, C. C.; Ying, K. C.; Lin, S. W., Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times, Computers & Industrial Engineering, 74, 102-110 (2014)
[31] Lu, M.; Shen, Z. M., A review of robust operations management under model uncertainty, Production and Operations Management (2020)
[32] Luo, F.; Mehrotra, S., Distributionally robust optimization with decision dependent ambiguity sets, Optimization Letters, 14, 8, 2565-2594 (2020) · Zbl 1460.90121
[33] Mak, H. Y.; Rong, Y.; Zhang, J. W., Appointment scheduling with limited distributional information, Management Science, 61, 2, 316-334 (2015)
[34] Mulvey, J. M.; Vanderbei, R. J.; Zenios, S. A., Robust optimization of large-scale systems, Operations research, 43, 2, 264-281 (1995) · Zbl 0832.90084
[35] Natarajan, K.; Sim, M.; Uichanco, J., Asymmetry and ambiguity in newsvendor models, Management Science, 64, 7, 3146-3167 (2018)
[36] Niu, S.; Song, S.; Ding, J.-Y.; Zhang, Y.; Chiong, R., Distributionally robust single machine scheduling with the total tardiness criterion, Computers & Operations Research, 101, 13-28 (2019) · Zbl 1458.90339
[37] Novak, A.; Gnatowski, A.; Sucha, P., Distributionally robust scheduling algorithms for total flow time minimization on parallel machines using norm regularizations, European Journal of Operational Research (2022) · Zbl 1507.90066
[38] Noyan, N.; Rudolf, G.; Lejeune, M., Distributionally robust optimization with decision-dependent ambiguity set, Optimization Online (2018)
[39] Oyetunji, E. O.; Oluleye, A. E.; Akande, S. A., Approximation algorithms for minimizing sum of flow time on a single machine with release dates, International Journal of Modern Engineering Research, 23, 687-696 (2012)
[40] Pei, Z.; Lu, H.; Jin, Q.; Zhang, L., Target-based distributionally robust optimization for single machine scheduling, European Journal of Operational Research, 299, 2, 420-431 (2022) · Zbl 1490.90146
[41] Pinedo, M., Scheduling: Theory, algorithms, and systems (2016), Springer · Zbl 1332.90002
[42] Rahimian, H., & Mehrotra, S. (2019). Distributionally robust optimization: A review. arXiv preprint arXiv:1908.05659. · Zbl 1492.90109
[43] Rockafellar, R. T.; Uryasev, S., Optimization of conditional value-at-risk, Journal of Risk, 3, 21-41 (2000)
[44] Rockafellar, R. T.; Uryasev, S., Conditional value-at-risk for general loss distributions, Journal of Banking & Finance, 1443-1471 (2002)
[45] Shabtay, D., Single-machine scheduling with machine unavailability periods and resource dependent processing times, European Journal of Operational Research (2021)
[46] Shabtay, D.; Mosheiov, G.; Oron, D., Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work, European Journal of Operational Research (2022) · Zbl 1507.90069
[47] Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on stochastic programming: Modeling and theory (2014), SIAM · Zbl 1302.90003
[48] Shehadeh, K. S.; Cohn, A. E.M.; Jiang, R., A distributionally robust optimization approach for outpatient colonoscopy scheduling, European Journal of Operational Research, 283, 2, 549-561 (2020) · Zbl 1431.90075
[49] Sidney, J. B., Optimal single-machine scheduling with earliness and tardiness penalties, Operations Research, 25, 1, 62-69 (1977) · Zbl 0383.90055
[50] Soroush, H. M., Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem, European Journal of Operational Research, 181, 1, 266-287 (2007) · Zbl 1121.90064
[51] van den Akker, M.; Hoogeveen, H., Minimizing the number of late jobs in a stochastic setting using a chance constraint, Journal of Scheduling, 11, 1, 59-69 (2008) · Zbl 1168.90484
[52] Wang, X.; Cheng, T. C.E., Single machine scheduling with resource dependent release times and processing times, European Journal of Operational Research, 162, 3, 727-739 (2005) · Zbl 1065.90045
[53] Wang, Y.; Zhang, Y.; Tang, J., A distributionally robust optimization approach for surgery block allocation, European Journal of Operational Research, 273, 2, 740-753 (2019)
[54] Yu, X.; Shen, S., Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets, Mathematical Programming, 1-40 (2020)
[55] Yue, F.; Song, S. J.; Zhang, Y. L.; Gupta, J. N.; Chiong, R., Robust single machine scheduling with uncertain release times for minimising the maximum waiting time, International Journal of Production Research, 56, 16, 5576-5592 (2018)
[56] Zhang, L.; Lu, L.; Yuan, J., Single machine scheduling with release dates and rejection, European Journal of Operational Research, 198, 3, 975-978 (2009) · Zbl 1176.90255
[57] Zhang, Y.; Baldacci, R.; Sim, M.; Tang, J., Routing optimization with time windows under uncertainty, Mathematical Programming, 175, 1-2, 263-305 (2019) · Zbl 1412.90100
[58] Zhu, S. S.; Fukushima, M., Worst-case conditional value-at-risk with application to robust portfolio management, Operations Research, 57, 5, 1155-1168 (2009) · Zbl 1233.91254
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.