No Access

The Minmax Regret Scheduling-Location Problem on Trees with Interval-Data Edge Lengths

Faculty of Fundamental Sciences, Van Lang University, 69/68 Dang Thuy Tram Street, Ward 13, Binh Thanh District, Ho Chi Minh City, Vietnam

E-mail Address: huy.lm@vlu.edu.vn

Corresponding author.

Search for more papers by this author

Kien Trung Nguyen

https://orcid.org/0000-0002-7522-4557

Department of Mathematics, Teacher College, Can Tho University, 3/2 Street, Can Tho City, Vietnam

E-mail Address: trungkien@ctu.edu.vn

Search for more papers by this author

, and

Liem Dinh Tien

Faculty of Fundamental Sciences, Van Lang University, 69/68 Dang Thuy Tram Street, Ward 13, Binh Thanh District, Ho Chi Minh City, Vietnam

E-mail Address: liem.dt@vlu.edu.vn

Search for more papers by this author

https://doi.org/10.1142/S0217595924500027Cited by:0 (Source: Crossref)

Abstract

We address in this paper a variant of the scheduling-location (ScheLoc) problem on tree networks with interval edge lengths where the total deviation of the uncertain data cannot exceed a threshold. We further use the minmax regret concept to deal with the corresponding uncertainty. In order to solve the problem, we investigate the structure of the schedule which leads to the maximum regret value at a fixed point. Then we consider the machine location belonging to a specific edge of the tree and partition the underlying edge into regions with linear maximum regret function. Finally, we develop a combinatorial algorithm that solves the minmax regret ScheLoc problem in polynomial time based on a finite dominating set approach.

Keywords:

References

Averbakh, I and O Berman (2000). Algorithms for the robust 1-center problem on a tree. European Journal of Operations Research, 123, 292–302. Crossref, Web of Science, Google Scholar
Bachtler, O, SO Krumke and HM Le (2020). Robust single machine makespan scheduling with release date uncertainty. Operations Research Letters, 48, 816–819. Crossref, Web of Science, Google Scholar
Ben-Tal, A, A Nemirovski and L El-Ghaoui (2009). Robust Optimization. New Jersey: Princeton University Press. Crossref, Google Scholar
Bertsimas, D, DB Brown and C Caramanis (2011). Theory and applications of robust optimization. SIAM Review, 53(3), 464–501. Crossref, Web of Science, Google Scholar
Brucker, P (2007). Scheduling Algorithms. Heidelberg: Springer Verlag. Google Scholar
Choi, BC, MJ Park, KM Kim and Y Min (2021). A parallel machine scheduling problem maximizing total weighted early work. Asia-Pacific Journal of Operational Research, 38(6), 2150007. Link, Web of Science, Google Scholar
Chen, B and CS Lin (1998). Minmax-regret robust 1-median location on a tree. Networks, 31, 93–103. Crossref, Web of Science, Google Scholar
Daskin, MS (1995). Network and Discrete Location: Models, Algorithms and Applications. New Jersey: Wiley. Crossref, Google Scholar
Elvikis, D, HW Hamacher and MT Kalsch (2009). Simultaneous scheduling and location (ScheLoc): The planar ScheLoc makespan problem. Journal of Scheduling, 12, 361–374. Crossref, Web of Science, Google Scholar
Franco, C, N Herazo-Padilla and JA Castañeda (2022). A queueing network approach for capacity planning and patient scheduling: A case study for the COVID-19 vaccination process in Colombia. Vaccine, 40(49), 7073–7086. Crossref, Web of Science, Google Scholar
Hakimi, SL (1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3), 450–459. Crossref, Google Scholar
Hennes, H and HW Hamacher (2007). Integrated scheduling and location models: Single machine makespan problems. Studied Locational Analysis, 16, 77–90. Google Scholar
Hennes, H (2005). Integration of Scheduling and Location Models. Aachen: Shaker Verlag. Google Scholar
Heßler, C (2016). Scheduling-Location Algorithms with Application in Evacuation Planning. München: Dr. Hut Verlag. Google Scholar
Kalsch, MT (2009). Scheduling-Location (ScheLoc): Models, Theory and Algorithms. München: Dr. Hut Verlag. Google Scholar
Kalsch, MT and Z Drezner (2010). Solving scheduling and location problems in the plane simultaneously. Computers and Operations Research, 37(2), 256–264. Crossref, Web of Science, Google Scholar
Kasperski, A and P Zielinski (2014). Minmax (regret) scheduling problems. In Sequencing and Scheduling with Inaccurate Data, YN Sotskov and FW Werner (Eds.), pp. 159–210. New York: Nova Science Publishers Inc. Google Scholar
Kouvelis, P and G Yu (1997). Robust Discrete Optimization and Its Applications. Massachusetts, MA: Kluwer Academic Publishers. Crossref, Google Scholar
Krumke, SO and HM Le (2020). Robust absolute single machine makespan scheduling-location problem on trees. Operations Research Letters, 48, 29–32. Crossref, Web of Science, Google Scholar
Lenstra, JK, AHG Rinnooy Kan and P Brucker (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362. Crossref, Google Scholar
Lu, CC, SW Lin and KC Ying (2012). Robust scheduling on a single machine to minimize total flow time. Computers and Operations Research, 39(3), 1682–1691. Crossref, Google Scholar
Mirchandani, PB and RL Francis (1990). Discrete Location Theory. New York: Wiley. Google Scholar
Nguyen, KT and A Chassein (2015). The Inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance. European Journal of Operational Research, 247(3), 774–781. Crossref, Web of Science, Google Scholar
Nhan, THN, KT Nguyen and H Nguyen-Thu (2022). Reverse 1-median problem on trees with uncertain vertex weights. Asia-Pacific Journal of Operational Research, 40(3), 2250033. Link, Google Scholar
Nickel, S and J Puerto (2008). Location Theory. Berlin: Springer Verlag. Google Scholar
Pinedo, ML (2008). Scheduling: Theory, Algorithms, and Systems. New York: Prentice Hall. Google Scholar
Soyster, AL (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 21, 1154–1157. Crossref, Web of Science, Google Scholar
Tang, L, Y Li, D Bai, T Liu and LC Coelho (2022). Bi-objective optimization for a multi-period COVID-19 vaccination planning problem. Omega, 110, 102617. Crossref, Web of Science, Google Scholar
Vahedi-Nouri, B, R Tavakkoli-Moghaddam, Z Hanzálek and A Dolgui (2022). Workforce planning and production scheduling in a reconfigurable manufacturing system facing the COVID-19 pandemic. Journal of Manufacturing Systems, 63, 563–574. Crossref, Web of Science, Google Scholar
Wang, JB, J Xue, B Cui and M Gao (2022). Single-machine scheduling problems with variable processing times and past-sequence-dependent delivery times. Asia-Pacific Journal of Operational Research, 39(2), 2150013. Link, Web of Science, Google Scholar
Zhang, C, Y Li, J Cao and X Wen (2022). On the mass COVID-19 vaccination scheduling problem. Computers & Operations Research, 141, 105704. Crossref, Web of Science, Google Scholar