Logo PTI Logo FedCSIS

Proceedings of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 25

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

DOI: http://dx.doi.org/10.15439/2021F66

Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 221–225 ()

Full text

Abstract. The problem of minimizing the maximum delivery times  on the single processor is a classical combinatorial optimization problem. The problem is denoted by 1|rj,qj|Cmax, has many applications, and it is NP-hard in stronge sense.  The goal of this paper is to propose a new 3/2-approximation 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.

References

  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.