Minimizing Tardiness in a Scheduling Environment with Jobs' Hierarchy

• Autorzy: Sinai Michal , Tamir Tami

Identyfikatory

DOI

10.15439/2021F36

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

Abstrakty

EN

In many scheduling environments, some jobs have higher priority than others. We consider a new model, motivated by real-life behavior, in which the priority among jobs is defined by a dominance hierarchy. Specifically, the jobs are arranged in hierarchy levels, and high ranking jobs are ready to accept only outcomes in which the service they receive is better than the service of subordinate jobs. We define the model and the set of feasible schedules formally, and provide algorithms and hardness proofs for two classical problems: minimizing the maximal tardiness and minimizing the number of tardy jobs. We provide optimal algorithms or hardness proofs for these problems, distinguishing between a global objective function and a multi-criteria objective.

Słowa kluczowe

EN

computational complexity; minimisation; scheduling

PL

złożoność obliczeniowa; minimalizacja; planowanie

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2021
• Tom: Vol. 25
• Strony: 201--209
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Sinai Michal

• School of Computer Science The Interdisciplinary Center Herzliya, Israel

autor

Tamir Tami

• School of Computer Science The Interdisciplinary Center Herzliya, Israel

Bibliografia

• 1. M. Adamu and A. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial and Management Optimization, 10:219–241, 2014.
• 2. A. Agnetis, F. Rossi, and S. Smriglio. Some results on shop scheduling with s-precedence constraints among job tasks. Algorithms, 12(12), 2019.
• 3. P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, Chris N. Potts, T. Tautenhahn, and S. L. van de Velde. Scheduling a batching machine. Journal of Scheduling, 1(1):31–54, 1998.
• 4. I.D. Chase, C. Tovey, and P. Murch, Two’s Company, Three’s a Crowd: Differences in Dominance Relationships in Isolated versus Socially Embedded Pairs of Fish. Behaviour. 140(10):1193–21, 2003.
• 5. G. Christodoulou, E. Koutsoupias and A. Nanavati, Coordination mechanisms, Theor. Comput. Sci., 410(36), 2009.
• 6. C. Ferguson and K. M. Beaver. Natural born killers: The genetic origins of extreme violence. Aggression and Violent Behavior. 14(5):286-–294, 2009.
• 7. M. C. Fields and G. N. Frederickson. A faster algorithm for the maximum weighted tardiness problem. Information Processing Letters, 36(1):39–44, 1990.
• 8. M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
• 9. L. R. Gesquiere, N. H .Learn, M. C.Simao, P. O. Onyango, S. C. Alberts, and J. Altmann. Life at the top: rank and stress in wild male baboons. Science (New York, N.Y.), 333(6040), 357–360, 2011.
• 10. 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. Discrete Math, 5:287–326, 1979.
• 11. D. Hermelin, S. Karhi, M. Pinedo, and D. Shabtay. New algorithms for minimizing the weighted number of tardy jobs on a single machine. Annals of Operations Research, Springer, 298(1):271–287, 2012.
• 12. D. Hochbaum and R. Shamir. An O(nlog 2 n) algorithm for the maximum weigthed tardiness problem. Information Processing Letters, 31(4):215–219, 1989.
• 13. R.M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85–103, 1972.
• 14. E.S. Kim and M. E. Posner. Parallel machine scheduling with s-precedence constraints. IIE Transactions, 42(7):525–537, 2010.
• 15. E.L. Lawler. Optimal sequencing of a single machine subject to precedence constraints. Management Sci., 19:544–546, 1973.
• 16. E.L. Lawler and J.M. Moore. A functional equation and its application to resource allocation and sequencing problems. Management Sci., 16(1):77–84, 1969.
• 17. J.M. Moore. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Sci., 15:102–109, 1968.
• 18. M. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2008.
• 19. S. K. Sahni. Algorithms for scheduling independent tasks. Journal of Assoc. Comput. Mach,, 23:116–127, 1976.
• 20. T. Tamir. Scheduling with bully selfish jobs. Theory Comput. Syst., 50(1):124–146, 2012.
• 21. B. Vöcking. Algorithmic Game Theory, chapter 20: Selfish Load Balancing. Cambridge University Press, 2007.

Uwagi

1. Track 1: Artificial Intelligence in Applications

2. Session: 14th International Workshop on Computational Optimization