Multi-agent scheduling on a single machine with max-form criteria. (English) Zbl 1129.90023

Summary: We consider multi-agent scheduling on a single machine, where the objective functions of the agents are of the max-form. For the feasibility model, we show that the problem can be solved in polynomial time even when the jobs are subject to precedence restrictions. For the minimality model, we show that the problem is strongly NP-hard in general, but can be solved in pseudo-polynomial-time when the number of agents is a given constant. We then identify some special cases of the minimality model that can be solved in polynomial-time.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI Link


[1] Agnetis, A.; Mirchandani, P.B.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Operations research, 52, 229-242, (2004) · Zbl 1165.90446
[2] Baker, K.R.; Smith, J.C., A multiple-criterion model for machine scheduling, Journal of scheduling, 6, 7-16, (2003) · Zbl 1154.90406
[3] Brucker, P., Scheduling algorithms, (2001), Springer Verlag Berlin · Zbl 1051.90011
[4] Curiel, I.; Pederzoli, G.; Tijs, S., Sequencing games, European journal of operational research, 40, 344-351, (1989) · Zbl 0674.90107
[5] Du, J.; Leung, J.Y.-T., Minimizing total tardiness on one machine is NP-hard, Mathematics of operations research, 15, 483-495, (1990) · Zbl 0714.90052
[6] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[7] Hamers, H.; Borm, P.; Tijs, S., On games corresponding to sequencing situations with ready times, Mathematical programming, 70, 1-13, (1995) · Zbl 0844.90120
[8] Kim, K., Paulson, B.C., Petrie, C.J., Lesser, V.R., 1999. Compensatory negotiation for agent-based project schedule coordination. CIFE working paper #55, Stanford University, Stanford, CA.
[9] Kovalyov, M.Y.; Ng, C.T.; Cheng, T.C.E., Fixed interval scheduling: models, applications, computational complexity and algorithms, European journal of operational research, 178, 331-342, (2007) · Zbl 1107.90019
[10] Lawler, E.L., Optimal sequencing of a single machine subject to precedence constraints, Management science, 19, 544-546, (1973) · Zbl 0254.90039
[11] Lawler, E.L., A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness, Annals of discrete mathematics, 1, 331-342, (1977) · Zbl 0353.68071
[12] Scharbrodt, M.; Steger, A.; Weisser, H., Approximability of scheduling with fixed jobs, Journal of scheduling, 2, 267-284, (1999) · Zbl 0953.90025
[13] Schultz, D., Oh, S.-H., Grecas, C.F., Albani, M., Sanchez, J., Arbib, C., Arvia, V., Servilio, M., Del Sorbo, F., Giralda, A., Lombardi, G., 2002. A QoS concept for packet oriented S-UMTS services. In: Proceedings of the 1st Mobile Summit, Thessaloniki, Greece.
[14] Yuan, J.J.; Shang, W.P.; Feng, Q., A note on the scheduling with two families of jobs, Journal of scheduling, 8, 537-542, (2005) · Zbl 1123.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.