Worst-Case Analysis of an Approximation Algorithm for Single Machine Scheduling Problem

• Autorzy: Grigoreva Natalia

Identyfikatory

DOI

10.15439/2021F66

• Konferencja: Federated Conference on Computer Science and Information Systems (16 ; 02-05.09.2021 ; online)
• Języki publikacji: EN

Abstrakty

EN

—The problem of minimizing the maximum delivery times while scheduling jobs on the single processor is a classical combinatorial optimization problem. This problem is denoted by 1|rj,qj|Cmax has many applications, and it is NP-hard in strong sense. The goal of this paper is to propose a new 3/2approximation algorithm, which runs in O(n log n) time. We proved that the bound of 3/2 is tight. To check the efficiency of the algorithm we tested it on random generated problems of up to 5000 jobs.

Słowa kluczowe

EN

single machine scheduling problems; release time; delivery time; approximation algorithm; worst-case performance ratio

PL

problem jednomaszynowy; czas wydania; czas dostawy; algorytm aproksymacyjny; analiza najgorszego przypadku

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2021
• Tom: Vol. 25
• Strony: 221--225
• Opis fizyczny: Bibliogr. 18 poz., wz., tab.

Twórcy

autor

Grigoreva Natalia

• St.Petersburg State University Universitetskay nab. 7/9, St.Petersburg, Russia

Bibliografia

• 1. C. Artigues and D.Feillet, "A branch and bound method for the job-shop problem with sequence-dependent setup times," Ann. of Oper. Res., vol. 159, 2008, pp. 135–159, http://dx.doi.org/10,1287/opre.49.6.854.10014.
• 2. K.R. Baker, Introduction to Sequencing and Scheduling. John Wiley & Son, New York, 1974.
• 3. J. Carlier, "The one machine sequencing problem," European Journal of Operational Research, vol.11, 1982, pp.42—47, http://dx.doi.org/10.1016/s0377-2217(82)80007-6.
• 4. C. Chandra, Z. Liu, J. He, T. Ruohonen, "A binary branch and bound algorithm to minimize maximum scheduling cost," Omega , vol. 42, 2014, pp. 9–15, http://dx.doi.org/10.1016/j.omega2013.02.005.
• 5. R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: A survey," Ann. of Disc. Math. ,vol. 5, no. 10, 1979, pp. 287–326, http://dx.doi.org/10.1016/S0167-5060(08)70356-X.
• 6. N. Grigoreva, "Single Machine Inserted Idle Time Scheduling with Release Times and Due Dates," Proc. DOOR2016. Vladivostoc. Russia. Sep.19-23.2016. Ceur-WS, vol. 1623, 2016, pp. 336–343.
• 7. N.S Grigoreva, "Single Machine Scheduling with Precedence Constrains, Release and Delivery times", in Proceedings of 40th Anniversary International Conference on Information Systems Architecture and Technology–ISAT 2019- Part III. (Advances in Intelligent Systems and Computing, v. 1052), pp. 188 –198, http://dx.doi.org/10.1007/978-3-030-30443-0-17.
• 8. L.A. Hall and D.B. Shmoys, "Jackson’s rule for single-machine scheduling: making a good heuristic better," Mathematics of Operations Research, 17 (1) , 1992, pp. 22–35.
• 9. J. J. Kanet and V.Sridharan, "Scheduling with inserted idle time: problem taxonomy and literature review", Operations Research, vol. 48, 2000, no. 1, pp. 99–110, http: //dx.doi.org/10.1287/opre.48.1.111.12453.
• 10. H. Kise, T. Ibaraki and H. Mine, "Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times", Journal of the Operations Research Society of Japan, vol. 22, 1979, pp. 205–224.
• 11. J.K. Lenstra, A.H.G. Rinnooy Kan and P.Brucker, "Complexity of machine scheduling problems," Ann. of Disc. Math., 1, 1977, pp. 343–362, http://dx.doi.org/10.1016/s0167-5060(08)707-43-X.
• 12. Y. Li, E. Fadda, D. Manerba, R.Tadei and O. Terzo, "Reinforcement Learning Algorithms for Online Single-Machine Scheduling", Proceedings of the 2020 Federated Conference on Computer Science and Infor- mation Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds), ACSIS, vol. 21, 2020, pp. 277–283, http://dx.doi.org/10.15439/2020F100
• 13. Z. Liu, "Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints," Computers & Operations Research, vol. 37, 2010, pp. 1537–1543, http://dx.doi.org/10.1016/j.cor.2009.11.008.
• 14. E. Nowicki and C. Smutnicki, "An approximation algorithm for a single-machine scheduling problem with release times and delivery times", Discrete Applied Mathematics, 48, 1994, pp. 69–79, http://dx.doi.org/10.1016/0166-218X(92)00110-8.
• 15. Y. Pan, L. Shi, "Branch and bound algorithm for solving hard instances of the one-machine sequencing problem",European Journal of Operational Research, 168, 2006, pp. 1030–1039, http://dx.doi.org/10.1016/j.ejor.2004.07.050.
• 16. C.N. Potts, "Analysis of a heuristic for one machine sequencing with release dates and delivery times", Operations Research, 28, 1980, pp. 1436–1441, http://dx.doi.org/10.1287/opre.28.6.1436.
• 17. L. Schrage, "Optimal Solutions to Resource Constrained Network Scheduling Problems", (unpublished) 1971.
• 18. K. Sourirajan and R. Uzsoy, "Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication," J. Sched. 10, 2007, pp. 41–65, http://dx.doi.org/10.1007/s10951-006-0325-5.

Uwagi

1. Track 1: Artificial Intelligence in Applications

2. Session: 14th International Workshop on Computational Optimization

3. Short Paper