×

The distributionally robust machine scheduling problem with job selection and sequence-dependent setup times. (English) Zbl 1458.90263

Summary: This paper proposes an interesting variant of the parallel machine scheduling problem with sequence-dependent setup times, where a subset of jobs has to be selected to guarantee a minimum profit level while the total completion time is minimized. The problem is addressed under uncertainty, considering both the setup and the processing times as random parameters. To deal with the uncertainty and to hedge against the worst-case performance, a risk-averse distributionally robust approach, based on the conditional value-at-risk measure, is adopted. The computational complexity of the problem is tackled by a hybrid large neighborhood search metaheuristic. The efficiency of the proposed method is tested via computational experiments, performed on a set of benchmark instances.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aksen, D.; Kaya, O.; Salman, F. S.; Tüncel, Ö., An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem, Eur. J. Oper. Res., 239, 2, 413-426 (2014) · Zbl 1339.90015
[2] Alimoradi, S.; Hematian, M.; Moslehi, G., Robust scheduling of parallel machines considering total flow time, Comput. Ind. Eng., 93, 152-161 (2016)
[3] Artzner, P.; Delbaen, F.; Eber, J. M.; Heath, D., Coherent measures of risk, Math. Finance, 9, 203-227 (1999) · Zbl 0980.91042
[4] Atakan, S.; Bulbul, K.; Noyan, N., Minimizng value-at-risk in single machine scheduling, Ann. Oper. Res., 248, 25-73 (2017) · Zbl 1357.90062
[5] Basak, S.; Shapiro, A., Value-at-risk-based risk management: optimal policies and asset prices, Rev. Financ. Stud., 14, 2, 371-405 (2001)
[6] Beraldi, P.; Bruni, M. E.; Laganá, D.; Musmanno, R., The risk-averse traveling repairman problem with profits, Soft. Comput., 9, 1-15 (2019) · Zbl 1418.90066
[7] Bertsimas, D.; Brown, D. B.; Caramanis, C., Theory and applications of robust optimization, SIAM Rev., 53, 3, 464-501 (2011) · Zbl 1233.90259
[8] Bertsimas, D.; Sim, M., The price of robustness, Oper. Res., 52, 1, 35-53 (2004) · Zbl 1165.90565
[9] Bougeret, M.; Pessoa, A. A.; Poss, M., Robust scheduling with budgeted uncertainty, Discrete Appl. Math., 261, 31, 93-107 (2019) · Zbl 1411.68181
[10] Bruni, M. E.; Beraldi, P.; Khodaparasti, S., A hybrid reactive GRASP heuristic for the risk-averse k-traveling repairman problem with profits, Comput. Oper. Res., 115, Article 104854 pp. (2020) · Zbl 1458.90066
[11] Bruni, M. E.; Khodaparasti, S.; Beraldi, P., The selective minimum latency problem under travel time variability: an application to post-disaster assessment operations, Omega, 22, Article 102154 pp. (2020) · Zbl 1458.90066
[12] Bruni, M.E., Khodaparasti, S., Beraldi, P., 2019. A Selective Scheduling Problem with Sequence-dependent setup Times: A Risk-averse Approach. In Proceedings of the 8th International Conference on Operations Research and Enterprise Systems ICORES 2019, pp. 195-201.
[13] Bruni, M. E.; Pugliese, L. D.P.; Beraldi, P.; Guerriero, F., An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations, Omega, 71, 66-84 (2017)
[14] Bruni, M. E.; Di Puglia Pugliese, L.; Beraldi, P.; Guerriero, F., A computational study of exact approaches for the adjustable robust resource-constrained project scheduling problem, Comput. Oper. Res., 99, 178-190 (2018) · Zbl 1458.90262
[15] Bruni, M.E., Di Puglia Pugliese, L., Beraldi, P., Guerriero, F., 2018. A Two-stage Stochastic Programming Model for the Resource Constrained Project Scheduling Problem under Uncertainty. ICORES 2018 - Proceedings of the 7th International Conference on Operations Research and Enterprise Systems 2018, pp. 194-200. · Zbl 1458.90262
[16] Cesaret, B.; Oğuz, C.; Salman, F. S., A tabu search algorithm for order acceptance and scheduling, Comput. Oper. Res., 39, 6, 1197-1205 (2012)
[17] Chang, Z.; Ding, J. Y.; Song, S., Distributionally robust scheduling on parallel machines under moment uncertainty, Eur. J. Oper. Res., 272, 3, 832-846 (2019) · Zbl 1403.90382
[18] Chang, Z.; Song, S.; Zhang, Y.; Ding, J. Y.; Zhang, R.; Chiong, R., Distributionally robust single machine scheduling with risk aversion, Eur. J. Oper. Res., 256, 1, 261-274 (2017) · Zbl 1394.90266
[19] Chaurasia, S. N.; Singh, A., Hybrid evolutionary approaches for the single machine order acceptance and scheduling problem, Appl. Soft Comput., 52, 725-747 (2017)
[20] Davari, M., Contributions to complex project and machine scheduling problems (2017), Faculty of Economics and Business, KU Leuven, (Ph.D. thesis)
[21] Davari, M.; Demeulemeester, E., A novel branch-and-bound algorithm for the chance-constrained resource-constrained project scheduling problem, Int. J. Prod. Res., 1-18 (2018)
[22] Emami, S., Moslehi, G., Sabbagh, M., 2017. A decomposition approach for order acceptance and scheduling problem: a robust optimization approach. Computat. Appl. Math. 36(4) 1471-151. · Zbl 1384.90044
[23] Ertem, M.; Ozcelik, F.; Saraç, T., Single machine scheduling problem with stochastic sequence-dependent setup times, Int. J. Prod. Res., 57, 10, 3273-3328 (2019)
[24] Geramipour, S.; Moslehi, G.; Reisi-Nafchi, M., Maximizing the profit in customer’s order acceptance and scheduling problem with weighted tardiness penalty, J. Oper. Res. Soc., 68, 1, 89-101 (2017)
[25] Giauque, W. C.; Hanses, J. V.; McDonald, J. B.; Pritchett, B. M., Selecting job scheduling algorithms: beta distribution model for service times, Int. J. Syst. Sci., 21, 2, 439-446 (1990) · Zbl 0687.68013
[26] Hall, N. G.; Posner, M. E., Generating experimental data for computational testing with machine scheduling applications, Oper. Res., 49, 6, 854-865 (2001) · Zbl 1163.90490
[27] Kasperski, A.; Zielinski, P., Risk-averse single-machine scheduling: complexity and approximation, J. Sched., 22, 567-580 (2019) · Zbl 1430.90270
[28] Liu, M.; Liu, X.; Chu, F.; Zheng, F.; Chu, C., Service-oriented robust parallel machine scheduling, Int. J. Prod. Res., 57, 12, 3814-3830 (2018)
[29] Lo, A. W., Semi-parametric upper bounds for option prices and expected payoffs, J. Financ. Econ., 19, 2, 373-387 (1987)
[30] Lu, C. C.; Lin, S. W.; Ying, K. C., Minimizing worst-case regret of makespan on a single machine with uncertain processing and setup times, Appl. Soft Comput., 23, 144-151 (2014)
[31] Malcolm, D. G.; Roseboom, J. H.; Clark, C. E.; Fazar, W., Application of a technique for research and development program evaluation, Oper. Res., 7, 5, 646-669 (1958) · Zbl 1255.90070
[32] Meloni, C., Pranzo, M., 2019. Expected shortfall for the makespan in activity networks under imperfect information. Flexible Service Manuf. J. (in press).
[33] Nguyen, S., A learning and optimizing system for order acceptance and scheduling, Int. J. Adv. Manuf. Technol., 86, 5-8, 2021-2036 (2016)
[34] Niu, S.; Song, S.; Ding, J. Y.; Zhang, Y.; Chiong, R., Distributionally robust single machine scheduling with the total tardiness criterion, Comput. Oper. Res., 101, 13-28 (2019) · Zbl 1458.90339
[35] Nucamendi, S., Martinez-Salazar, I., Bruni, M.E., Khodaparasti, S. 2020. Multi depot traveling repairman problem with multiple trips. Technical report.
[36] Oguz, C.; Salman, F. S.; Yalçn, Z. B., Order acceptance and scheduling decisions in make-to-order systems, Int. J. Prod. Econ., 125, 1, 200-211 (2010)
[37] Pereira, J., The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective, Comput. Oper. Res., 66, 141-152 (2016) · Zbl 1349.90387
[38] Pereira, M. A.; Coelho, L. C.; Lorena, L. A.; De Souza, L. C., A hybrid method for the probabilistic maximal covering location-allocation problem, Comput. Oper. Res., 57, 51-59 (2015) · Zbl 1348.90411
[39] Pisinger, D.; Ropke, S., A general heuristic for vehicle routing problems, Comput. Oper. Res., 34, 8, 2403-2435 (2007) · Zbl 1144.90318
[40] Pisinger, D.; Ropke, S., Large neighborhood search. In Handbook of metaheuristics, 399-419 (2010), Springer: Springer Boston, MA
[41] Ranjbar, M.; Davari, M.; Leus, R., Two branch-and-bound algorithms for the robust parallel machine scheduling problem, Comput. Oper. Res., 39, 7, 1652-1660 (2012) · Zbl 1251.90213
[42] Ribeiro, G. M.; Laporte, G., An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem, Comput. Oper. Res., 39, 3, 728-735 (2012) · Zbl 1251.90057
[43] Rockafeller, R. T., Coherent approaches to risk in optimization under uncertainty, INFORMS Tutorials in Operations Research, 38-61 (2007)
[44] Rockafellar, R. T.; Uryasev, S., Conditional value-at-risk for general loss distributions, J. Banking Finance, 26, 7, 1443-1471 (2002)
[45] Sarin, S. C.; Sherali, H. D.; Liao, L., Minimizing conditional-value-at-risk for stochastic scheduling problems, J. Sched., 17, 1, 5-15 (2014) · Zbl 1297.90067
[46] Shabtay, D.; Gaspar, N.; Kaspi, M., A survey on offline scheduling with rejection, J. Sched., 16, 1, 3-28 (2013) · Zbl 1297.90058
[47] Shaw, P., A new local search algorithm providing high quality solutions to vehicle routing problems (1997), APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scotland, UK
[48] Silva, Y. L.T.; Subramanian, A.; Pessoa, A. A., Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times, Comput. Oper. Res., 90, 142-160 (2018) · Zbl 1391.90319
[49] Slotnick, S. A., Order acceptance and scheduling: a taxonomy and review, Eur. J. Oper. Res., 212, 1, 1-11 (2011)
[50] Suwa, H.; Sandoh, H., Online scheduling in manufacturing: A cumulative delay approach (2012), Springer Science & Business Media
[51] Urgo, M.; Váncza, J., A branch-and-bound approach for the single machine maximum lateness stochastic scheduling problem to minimize the value-at-risk, Flex Serv. Manuf. J., 31, 472-496 (2019)
[52] Van Parys, B.P., Esfahani, P.M., Kuhn, D., 2017. From data to decisions: Distributionally robust optimization is optimal. arXiv preprint arXiv:1704.04118.
[53] Wang, J.; Demeulemeester, E.; Qiu, D., A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds, Comput. Oper. Res., 74, 1-13 (2016) · Zbl 1349.90895
[54] Wang, S.; Ye, B., Exact methods for order acceptance and scheduling on unrelated parallel machines, Comput. Oper. Res., 104, 159-173 (2019) · Zbl 1458.90369
[55] Wu, G. H.; Cheng, C. Y.; Yang, H. I.; Chena, C. T., An improved water flow-like algorithm for order acceptance and scheduling with identical parallel machines, Appl. Soft Comput., 71, 1072-1084 (2018)
[56] Xia, Y.; Chen, B.; Yue, J., Job sequencing and due date assignment in a single machine shop with uncertain processing times, Eur. J. Oper. Res., 184, 1, 63-75 (2008) · Zbl 1152.90004
[57] Xie, X.; Wang, X., An enhanced ABC algorithm for single machine order acceptance and scheduling with class setups, Appl. Soft Comput., 44, 255-266 (2016)
[58] Xu, X.; Cui, W.; Lin, J.; Qian, Y., Robust makespan minimisation in identical parallel machine scheduling problem with interval data, Int. J. Prod. Res., 51, 12, 3532-3548 (2013)
[59] Xu, L.; Wang, Q.; Huang, S., Dynamic order acceptance and scheduling problem with sequence-dependent setup time, Int. J. Prod. Res., 53, 19, 5797-5808 (2015)
[60] Yue, F.; Song, S.; Zhang, Y.; Gupta, J. N.; Chiong, R., Robust single machine scheduling with uncertain release times for minimising the maximum waiting time, Int. J. Prod. Res., 56, 16, 5576-5592 (2018)
[61] Zhang, Y.; Shen, Z. J.M.; Song, S., Exact algorithms for distributionally \(\beta \)-robust machine scheduling with uncertain processing times, INFORMS J. Comput., 30, 4, 662-676 (2018) · Zbl 1448.90046
[62] Zhong, X.; Ou, J.; Wang, G., Order acceptance and scheduling with machine availability constraints, Eur. J. Oper. Res., 232, 3, 435-441 (2014) · Zbl 1305.90208
[63] Zhu, S.; Fukushima, M., Worst-case conditional value-at-risk with application to robust portfolio management, Oper. Res., 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.