We study the worst case performance guarantee of locally optimal solutions for the problem of scheduling jobs on uniformly related parallel machines with the objective of minimizing the total weighted completion time. The quality of locally optimal solutions under the jump neighborhood is analyzed, which consists of iteratively moving a single job from one machine to another, improving the total weighted completion time in each iteration and stopping once improvement is no longer possible. We propose an upper bound for the total weighted completion time for the solutions obtained by this local search, and upper and lower bounds for the performance guarantee of the obtained locally optimal solutions. Additionally, the case of identical parallel machines is analyzed.
Keywords: Parallel machines, total weighted completion time, local search, performance guarantee
@article{RO_2022__56_2_1079_0,
author = {Mu\~noz, Felipe T. and Pinochet, Alejandro A.},
title = {Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines},
journal = {RAIRO. Operations Research},
pages = {1079--1088},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {2},
doi = {10.1051/ro/2022045},
mrnumber = {4407599},
zbl = {1487.90310},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022045/}
}
TY - JOUR AU - Muñoz, Felipe T. AU - Pinochet, Alejandro A. TI - Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines JO - RAIRO. Operations Research PY - 2022 SP - 1079 EP - 1088 VL - 56 IS - 2 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022045/ DO - 10.1051/ro/2022045 LA - en ID - RO_2022__56_2_1079_0 ER -
%0 Journal Article %A Muñoz, Felipe T. %A Pinochet, Alejandro A. %T Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines %J RAIRO. Operations Research %D 2022 %P 1079-1088 %V 56 %N 2 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022045/ %R 10.1051/ro/2022045 %G en %F RO_2022__56_2_1079_0
Muñoz, Felipe T.; Pinochet, Alejandro A. Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines. RAIRO. Operations Research, Tome 56 (2022) no. 2, pp. 1079-1088. doi: 10.1051/ro/2022045
[1] , and , Optimal coordination mechanisms for multi-job scheduling games. In: ESA (2014). | MR | Zbl
[2] , , and , A survey of very large-scale neighborhood search techniques. Disc. Appl. Math. 123 (2002) 75–102. | MR | Zbl | DOI
[3] , A survey of approximation results for local search algorithms. In: Efficient Approximation and Online Algorithms, edited by , and . Springer (2006) 30–73. | MR | Zbl
[4] , and , Lift-and-round to improve weighted completion time on unrelated machines. In: STOC (2016). | MR
[5] , and , Improving local search heuristics for some scheduling problems. Part II. Disc. Appl. Math. 72 (1997) 47–69. | MR | Zbl | DOI
[6] , and , Quality of move-optimal schedules for minimizing total weighted completion time. Oper. Res. Lett. 34 (2006) 583–590. | MR | Zbl | DOI
[7] , , and , Exponential size neighborhoods for makespan minimization scheduling. Naval Res. Logist. 58 (2011) 795–803. | MR | Zbl | DOI
[8] , and , Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17 (1974) 382–387. | MR | Zbl | DOI
[9] and , Bounds for list schedules on uniform processors. SIAM J. Comput. 9 (1980) 91–103. | MR | Zbl | DOI
[10] , , , and , Decentralized utilitarian mechanisms for scheduling games. Games Econ. Behav. 92 (2015) 306–326. | MR | Zbl | DOI
[11] , and , Theory of Scheduling. Addison-Wesley (1967). | MR | Zbl
[12] and , Performance guarantees of local search for minsum scheduling problems. Math. Program. (2020). | DOI | MR | Zbl
[13] , and , Bounds for the optimal scheduling of jobs on processors. Manage Sci. 11 (1964) 268–279. | MR | DOI
[14] and , Approximation schemes for scheduling on uniformly related and identical parallel machines. Algorithmica 39 (2004) 43–57. | MR | Zbl | DOI
[15] and , A linear time approximation algorithm for multiprocessor scheduling. BIT Numer. Math. 19 (1979) 312–320. | MR | Zbl | DOI
[16] , and , A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems. J. Comb. Optim. 8 (2004) 195–220. | MR | Zbl | DOI
[17] and , Strong NP-completeness results: Motivation, examples, and implications. J. ACM 25 (1978) 499–508. | MR | Zbl | DOI
[18] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman and Co., San Francisco (1979). | Zbl
[19] , , and , Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Disc. Math. 5 (1979) 287–326. | MR | Zbl | DOI
[20] , Minimizing average flow time with parallel machines. Oper. Res. 21 (1973) 846–847. | Zbl | DOI
[21] and , Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23 (1976) 317–327. | MR | Zbl | DOI
[22] , and , Complexity of machine scheduling problems. Ann. Disc. Math. 1 (1977) 343–362. | MR | Zbl | DOI
[23] , Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. In: FOCS (2017). | MR
[24] , and , Theoretical Aspects of Local Search. Springer Science & Business Media, Berlin (2007). | MR | Zbl
[25] , , and , Performance guarantees of jump neighborhoods on restricted related parallel machines. Oper. Res. Lett. 40 (2012) 287–291. | MR | Zbl | DOI
[26] and , Performance guarantees of local search for multiprocessor scheduling. INFORMS J. Comput. 19 (2007) 52–63. | MR | Zbl | DOI
[27] and , A PTAS for minimizing the total weighted completion time on identical parallel machines. Math. Oper. Res. 25 (2000) 63–75. | MR | Zbl | DOI
[28] , Various optimizers for single-stage production. Naval Res. Logist. 3 (1956) 59–66. | MR | DOI
Cité par Sources :
