Abstract
This paper considers the online scheduling problem on m (m ≥ 3) parallel machines (the first k machines with grade 1 and the remaining m − k machines with grade 2) with two GoS levels and makespan as the objective function. The jobs arrive over time with grade 1 or 2 and an arrival job can be assigned to a machine only when the grade of the job is no less than the grade of the machine. Three cases are considered: (i) For k = 1, the authors present an online algorithm with competitive ratio of 9/5. (ii) For 1 < k < m − 1, an online algorithm with competitive ratio of 2.280 is proposed. (iii) For k = m − 1, an online algorithm is presented with competitive ratio of 2. All the three algorithms are based on greedy algorithm with a similar structure. At last, numerical instances are given and the average competitive ratios of the instances show good performance of the proposed algorithms.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Mokotoff E, Parallel machine scheduling problems: A survey, Asia-Pacific Journal of Operational Research, 2001, 18(2): 193–242.
Franca P M, Gendreau M, Laporte G, et al., A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective, Computers & operations research, 1994, 21(2): 205–210.
Cheng R and Gen M, Parallel machine scheduling problems using memetic algorithms, Computers & Industrial Engineering, 1997, 33(3-4): 761–764.
Chen Z L and Powell W B, Solving parallel machine scheduling problems by column generation, INFORMS Journal on Computing, 1999, 11(1): 78–94.
Chang P C, Chen S H, and Lin K L, Two-phase sub population genetic algorithm for parallel machine-scheduling problem, Expert Systems with Applications, 2005, 29(3): 705–712.
Grisselle C and Armacost R L, Parallel machine scheduling with release time and machine eligibility restrictions, Computers & Industrial Engineering, 1997, 33(1-2): 273–276.
Liao L W and Sheen G J, Parallel machine scheduling with machine availability and eligibility constraints, European Journal of Operational Research, 2008, 184(2): 458–467.
Edis E B and Ozkarahan I, A combined integer/constraint programming approach to a resource-constrained parallel machine scheduling problem with machine eligibility restrictions, Engineering Optimization, 2011, 43(2): 135–157.
Tseng C T, Lee C H, Chiu Y S P, et al., A discrete electromagnetism-like mechanism for parallel machine scheduling under a grade of service provision, International Journal of Production Research, 2017, 55(11): 3149–3163.
Jongho P, Chang S Y, and Lee K, Online and semi-online scheduling of two machines under a grade of service provision, Operations Research Letters, 2006, 34(6): 692–696.
Jiang Y W, He Y, and Tang C M, Optimal online algorithms for scheduling on two identical machines under a grade of service, Journal of Zhejiang University-Science, 2006, A7(3): 309–314.
Yong W, Ji M, and Yang Q F, Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision, International Journal of Production Economics, 2012, 135(1): 367–371.
Zhang A, Jiang Y W, and Tan Z Y, Online parallel machines scheduling with two hierarchies, Theoretical Computer Science, 2009, 410(38-40): 3597–3605.
Tan Z Y and Zhang A, A note on hierarchical scheduling on two uniform machines, Journal of Combinatorial Optimization, 2010, 20(1): 85–95.
Jiang Y W, Online scheduling on parallel machines with two GoS levels, Journal of Combinatorial Optimization, 2008, 16(1): 28–38.
Liu M, Xu Y, Chu C, et al., Online scheduling on two uniform machines to minimize the makespan, Theoretical Computer Science, 2009, 410(21-23): 2099–2109.
Marvin M and Shabtay Dvir, Scheduling unit length jobs on parallel machines with lookahead information, Journal of Scheduling, 2011, 14(4): 335–350.
Hong K S and Leung J Y T, On-line scheduling of real-time tasks, IEEE Transactions on Computers, 1992, 41(10): 1326–1331.
Chen B and Vestjens A, Scheduling on identical machines: How good is LPT in an online setting, Operations Research Letters, 1997, 21(4): 165–169.
John N and Seiden S S, An optimal online algorithm for scheduling two machines with release times, Theoretical Computer Science, 2001, 268(1): 133–143.
Grissele C and Armacost R L, Minimizing makespan on parallel machines with release time and machine eligibility restrictions, International Journal of Production Research, 2004, 42(6): 1243–1256.
Lee K, Joseph Y T L, and Pinedo M L, Scheduling jobs with equal processing times subject to machine eligibility constraints, Journal of Scheduling, 2011, 14(1): 27–38.
Xu J and Liu Z H, An optimal online algorithm for scheduling on two parallel machines with GoS eligibility constraints, Journal of the Operations Research Society of China, 2016, 4(3): 371–377.
Li S S and Zhang Y Z, On-line scheduling on parallel machines to minimize the makespan, Journal of Systems Science and Complexity, 2016, 29(2): 472–477.
Cai S, Liu A, and Liu K, Online scheduling of two identical machines under a grade of service provision, Control Conference (CCC), 2017 36th Chinese IEEE, 2017.
Shmoys D B, Joel W, and David P W, Scheduling parallel machines on-line, SIAM Journal on Computing, 1995, 24(6): 1313–1331.
Ou J, Joseph Y T L, and Chung L L, Scheduling parallel machines with inclusive processing set restrictions, Naval Research Logistics, 2008, 55(4): 328–338.
Huo Y and Joseph Y T L, Fast approximation algorithms for job scheduling with processing set restrictions, Theoretical Computer Science, 2010, 411(44-46): 3947–3955.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the National Natural Science Foundation of China under Grant Nos. 71390334 and 11271356.
Rights and permissions
About this article
Cite this article
Cai, S., Liu, K. Heuristics for Online Scheduling on Identical Parallel Machines with Two GoS Levels. J Syst Sci Complex 32, 1180–1193 (2019). https://doi.org/10.1007/s11424-019-7427-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-019-7427-6