Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

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

Minimizing the Number of Late Multi-Task Jobs on Identical Machines in Parallel

, ,

DOI: http://dx.doi.org/10.15439/2016F441

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 577–584 ()

Full text

Abstract. We consider the problem of scheduling multi-task jobs on identical machines in parallel. Each multi-task job consists of one or more tasks. Each job has a release date and a due date. A task of a job can be processed by any one of the machines. Multiple machines can process the tasks of a job concurrently. The completion time of a job is the time at which all its individual tasks have been completed. A job is late if it is completed after its due date. We study the problem of minimizing the total number of late jobs. We show that while some special cases are solvable, the general problem is NP-hard and there exists no polynomial time rho-approximation algorithm, for any rho > 1. We present a general algorithm for the problem and derive from it six heuristics

References

  1. J.-T. Leung, H. Li, and M. Pinedo, “Order scheduling models: an overview,” in Multidisciplinary Scheduling: Theory and Applications, G. Kendall, E. K. Burke, S. Petrovic, and M. Gendreau, Eds. Springer, 2005, pp. 37–53, http://dx.doi.org/10.1007/0-387-27744-7_3.
  2. J. Blocher and D. Chhajed, “The customer order lead-time problem on parallel machines,” Naval Research Logistics, vol. 43, pp. 629–654, 1996, http://dx.doi.org/10.1002/(SICI)1520-6750(199608)43:5<629::AID-NAV3>3.0.CO;2-7.
  3. J. Bruno, E. Coffman, and R. Sethi, “Scheduling independent tasks to reduce mean finishing time,” Communications of the ACM, vol. 17, no. 7, pp. 382–387, 1974, http://dx.doi.org/10.1145/361011.361064.
  4. J. Yang, “Scheduling with batch objectives,” Ph.D. dissertation, Industrial and Systems Engineering Graduate Program, The Ohio State University, Columbus, Ohio, 1998.
  5. J. Yang and M. Posner, “Scheduling parallel machines for the customer order problem,” Journal of Scheduling, vol. 8, no. 1, pp. 49–74, 2005, http://dx.doi.org/10.1007/s10951-005-5315-5.
  6. J.-T. Leung, H. Li, and M. Pinedo, “Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel,” Naval Research Logistics, vol. 53, no. 4, pp. 243–260, 2006, http://dx.doi.org/10.1002/nav.20138.
  7. J. Moore, “An n job, one machine sequencing algorithm for minimizing the number of late jobs,” Management Science, vol. 15, pp. 102–109, 1968, http://dx.doi.org/10.1287/mnsc.15.1.102.
  8. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. New York: W.H.Freeman, 1979.
  9. J. Lenstra, A. R. Kan, and P. Brucker, “Complexity of machine scheduling problems,” Annals of Discrete Mathematics, vol. 1, pp. 343–362, 1977, http://dx.doi.org/10.1016/S0167-5060(08)70743-X.
  10. E. Lawler, J. Lenstra, A. R. Kan, and D. Shmoys, “Sequencing and scheduling: algorithms and complexity,” in Handbooks in Operations Research and Management Science, 1993, pp. 445–522.
  11. P. Brucker, Scheduling Algorithms, Fifth Edition. Berlin: Springer, 2007.
  12. M. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer, 2008.
  13. E. Lawler, “A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs,” Annals of Operations Research, vol. 26, no. 1, pp. 125–133, 1990, http://dx.doi.org/10.1007/BF02248588.
  14. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.
  15. C. Papadimitriou and M. Yannakakis, “Optimization, approximation, and complexity classes,” in Journal of Computer and System Sciences, Vol. 43(3), pp. 425–440, 1991, http://dx.doi.org/10.1016/0022-0000(91)90023-X.
  16. R. Graham, “Bounds on multiprocessing timing anomalies,” SIAM Journal of Applied Mathematics, vol. 17, pp. 263–269, 1969, http://dx.doi.org/10.1137/0117039.
  17. E. Coffman, M. Garey, and D. Johnson, “Approximation algorithms for bin packing: a survey,” in Approximation Algorithms for NP-hard Problems, D. Hochbaum, Ed. PWS Publishers, 1997, pp. 46–93.
  18. J. Jackson, “Scheduling a production line to minimize maximum tardiness,” Management Science Research Project, UCLA, Tech. Rep. 43, 1955.
  19. J.-T. Leung, H. Li, and M. Pinedo, “Scheduling orders for multiple product types with due date related objectives,” European Journal of Operational Research, vol. 168, no. 2, pp. 370–389, 2006, http://dx.doi.org/10.1016/j.ejor.2004.03.030.