Complexity analyses for multi-agent scheduling problems with a global agent and equal length jobs. (English) Zbl 1387.90289
Summary: We study the scheduling of independent jobs where several agents compete to perform their jobs on common identical parallel machines: resource manager \(GA\) (global agent) wants to minimize a cost function associated with all jobs, while each agent \(k\) wants to have another cost function associated with its jobs not exceeding a given value \(Q_k\), \(k=1,\dots,K\). The jobs have equal processing requirements. Monotonic regular objective functions depending on the completion times of jobs are considered. The global cost function of agent \(GA\) may correspond to the global performance of the workshop independently on the agents objective functions. With various combinations of the objective functions, new complexity results are proposed and polynomial algorithms are derived to find an optimal solution that minimizes the global objective function, subject to the constraints that the objective functions of the other agents do not exceed a given threshold.
MSC:
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | T’kindt, V.; Billaut, J.-C., Multicriteria Scheduling, Models and Algorithms, Vol. 271 (2006), Springer · Zbl 1126.90002 |
| [2] | Agnetis, A.; Billaut, J.-C.; Gawiejnowicz, S.; Pacciarelli, D.; Soukhal, A., Multiagent Scheduling, Models and Algorithms (2014), Springer · Zbl 1286.90002 |
| [3] | Tuong, N. H.; Soukhal, A.; Billaut, J.-C., Single-machine multi-agent scheduling problems with a global objective function, J. Sched., 15, 3, 311-321 (2012) · Zbl 1280.90074 |
| [4] | Agnetis, A.; Mirchandani, P. B.; Pacciarelli, D.; Pacifici, A., Nondominated schedules for a job-shop with two competing users, Comput. Math. Organ. Theory, 2, 191-217 (2000) |
| [5] | Baker, K.; Smith, J.-C., A multiple-criterion model for machine scheduling, J. Sched., 6, 1, 7-16 (2003) · Zbl 1154.90406 |
| [6] | Pinedo, M., “Multiagent scheduling - Models and Algorithms”, by A. Agnetis, J.-C. Billaut, S. Gawiejnowicz, D. Pacciarelli, A. Soukhal, Eur. J. Oper. Res., 245, 3, 877-878 (2015) |
| [7] | Mavrotas, G., Effective implementation of the \(\epsilon \)-constraint method in multi-objective mathematical programming problems, Appl. Math. Comput., 213, 2, 455-465 (2009) · Zbl 1168.65029 |
| [8] | Pinedo, M., Scheduling. Theory, Algorithms, and Systems (2008), Springer-Verlag: Springer-Verlag Berlin · Zbl 1155.90008 |
| [9] | Brucker, P., Scheduling Algorithms (2005), Springer |
| [10] | Sadi, F.; Soukhal, A.; Billaut, J.-C., Solving multi-agent scheduling problems on parallel machines with a global objective function, RAIRO - Oper. Res., 48, 2, 255-269 (2014) · Zbl 1295.90012 |
| [11] | Yuan, J.; Shang, W.; Feng, Q., A note on the scheduling with two families of jobs, J. Sched., 8, 6, 537-542 (2005) · Zbl 1123.90040 |
| [12] | Cheng, T. C.E.; Ng, C. T.; Yuan, J. J., Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theoret. Comput. Sci., 362, 1, 273-281 (2006) · Zbl 1100.68007 |
| [13] | Agnetis, A.; Pitu, B.; Dario, P.; Andrea, P., Scheduling problems with two competing agents, Oper. Res., 52, 2, 229-242 (2004) · Zbl 1165.90446 |
| [14] | Balasubramanian, H.; Fowler, J.; Keha, A.; Pfund, M., Scheduling interfering job sets on parallel machines, European J. Oper. Res., 199, 1, 55-67 (2009) · Zbl 1176.90193 |
| [15] | Elvikis, D.; T’kindt, V., Two-agent scheduling on uniform parallel machines with min-max criteria, Ann. Oper. Res., 79-94 (2012) · Zbl 1296.90043 |
| [16] | Kravchenko, S.; Werner, F., Parallel machine problems with equal processing times: a survey, J. Sched., 14, 5, 435-444 (2011) · Zbl 1280.90058 |
| [17] | Lushchakova, I. N., Preemptive scheduling of equal length jobs with release dates on two uniform parallel machines, Discrete Optim., 6, 4, 446-460 (2009) · Zbl 1175.90180 |
| [19] | Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039 |
| [20] | Hopcroft, J.; Karp, R.-M., A \(n^{5 / 2}\) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 22-231 (1973) · Zbl 0266.05114 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
