Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 21

Proceedings of the 2020 Federated Conference on Computer Science and Information Systems

Multiprocessor Scheduling Problem with Release and Delivery Times

DOI: http://dx.doi.org/10.15439/2020F33

Citation: Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 21, pages 263–269 ()

Full text

Abstract. The multiprocessor scheduling problem is defined as follows: tasks have to be executed on several parallel identical processors. For each task we know release time, processing time and delivery time. At most one job can be processed at a time, but all jobs may be simultaneously delivered. Preemption on processors is not allowed. The objective is to minimize the time, by which all tasks are delivered. Scheduling tasks among parallel processors is a NP-hard problem in the strong sense. The best known approximation algorithm is Jackson's algorithm, which generates the list schedule by giving priority to the ready job with the largest delivery time. This algorithm generates no delay schedules. We define an IIT (inserted idle time) schedule as a feasible schedule in which a processor is kept idle at a time when it could begin processing a task. The paper proposes the approximation inserted idle time algorithm for the multiprocessor scheduling. It is proved that deviation of this algorithm from the optimum is smaller then twice the largest processing time. To illustrate the efficiency of our approach we compared two algorithms on randomly generated sets of jobs.

References

  1. C. Artigues, D. Feillet, "A branch and bound method for the job-shop problem with sequence-dependent setup times",Annals of Operations Research, vol. 159,2008, pp.135—159.
  2. K.R. Baker,Introduction to Sequencing and Scheduling. John Wiley & Son, New York, 1974.
  3. P. Brucker, Scheduling Algorithms. fifth ed. Springer,Berlin, 2007.
  4. J. Carlier, E. Néron, "An exact algorithm for solving the multiprocessor flowshop," RAIRO Operations Research, vol. 34, 2000, pp. 1—25.
  5. J. Carlier, "The one machine sequencing problem." European Journal of Operational Research,vol.11,1982, pp. 42–47.
  6. J. Carlier, E. Pinson, " Jackson’s pseudo preemptive schedule for the P m|rj, qj|Cmax scheduling problem," Annals of Operations Research, vol. 83, 1998, pp.41–58.
  7. J. Carlier, "Scheduling jobs with release dates and tails on identical machines to minimize the makespan."European Journal of Operational Research, vol. 29, 1987,pp.298—306.
  8. C. Chandra, Z.Liu, J. He, J,T. Ruohonen, "A binary branch and bound algorithm to minimize maximum scheduling cost," Omega, vol. 42, 2014„pp.9–15.
  9. A.,Gharbi, M.,Haouari, "Minimizing makespan on parallel machines subject to release dates and delivery times," Journal of Scheduling,vol. 5, 2002, pp.329—355.
  10. A. Gharbi, M. Haouari, "Optimal parallel machines scheduling with availability constraints,"Discrete Applied Mathematics vol. 148, 2005,
  11. A. Gharbi,M. Haouari, "An approximate decomposition algorithm for scheduling on parallel machines with heads and tails," Computers & Operations Research, vol. 34, 2007, pp.868 —883.
  12. R.L. Graham, E.L. Lawner, A.H.G. Rinnoy Kan, "Optimization and approximation in deterministic sequencing and scheduling," A survey.Ann. of Disc. Math., vol. 5 (10),1979, pp. 287–326.
  13. N.S.Grigoreva, "Branch and bound method for scheduling precedence constrained tasks on parallel identical processors", Lecture Notes in Engineering and Computer Science. In proc. of The World Congress on Engineering 2014, WCE 2014 London, U.K. 2014, pp.832–836.
  14. N.Grigoreva, "Single Machine Inserted Idle Time Scheduling with Release times and Due Dates," Proc.DOOR2016. Vladivostoc,Russia. Sep.19-23.2016. CEUR-WS.2016, vol.1623, pp. 336—343.
  15. D.Gusfield, "Bounds for naive multiple machine scheduling with release times and deadlines,"Journal of Algorithms vol.5,1984, pp.1—6.
  16. L.A.Hall, D.B. Shmoys, "Jackson’s rule for single-machine scheduling: making a good heuristic better," Mathematics of Operations Research. vol.17 (1),1992, pp.22–35.
  17. L.A.Hall,D.B. Shmoys, "Approximation schemes for constrained scheduling problems", Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 134 —139.
  18. M. Haouari, A. Gharbi, "Lower bounds for scheduling on identical parallel machines with heads and tails,"Annals of Operations Research vol. 129, 2004, pp.187—204.
  19. J. Kanet, V. Sridharan, "Scheduling with inserted idle time: problem taxonomy and literature review," Oper.Res. vol.48 (1),2000, pp. 99–110.
  20. J.A Lenstra, A.H.G. Rinnooy Kan, P. Brucker, "Complexity of machine scheduling problems,"Ann. of Disc. Math., vol. 1,1977, pp.343–362.
  21. M. Mastrolilli, "Efficient approximation schemes for scheduling problems with release dates and delivery times,"Journal of Scheduling, vol. 6, 2003, pp.521—531.
  22. E. Nowicki, C. Smutnicki, "An approximation algorithm for a single-machine scheduling problem with release times and delivery times," Discrete Applied Mathematics ,vol. 48, 1994, pp.69–79.
  23. J. Omer, A. Mucherino, "Referenced Vertex Ordering Problem", Theory, Applications and Solution Methods HAL open archives, hal-02509522, version 1, March, 2020.
  24. K. Sourirajan, R. Uzsoy, "Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication," Journal of Scheduling, vol. 10,2007, pp.41—65.
  25. 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.
  26. C.N. Potts, "Analysis of a heuristic for one machine sequencing with release dates and delivery times," Operational Research. vol. 28 (6), 1980, pp.445—462.
  27. J. Ullman, "NP-complete scheduling problems," J. Comp. Sys. Sci. vol. 171, 1975,pp. 394—394.
  28. Y. Zinder, D. Roper, "An iterative algorithm for scheduling unittime operations with precedence constraints to minimize the maximum lateness,"Annals of Operations Research, 81, 1998, pp. 321—340.
  29. Y. Zinder, " An iterative algorithm for scheduling UET tasks with due dates and release times,"European Journal of Operational Research, vol.149, 2003, pp. 404–416.