Combinatorial Mathematics; Fairness; Integer Programming; Multi-agent systems; Optimization Problems; Scheduling; Integer Program- ming; Optimization problems; Processing resources; Scheduling problem; Single-machine scheduling; System optimum; Total completion time; Two agents; Control and Systems Engineering
Abstract :
[en] We address a scheduling problem arising when two agents, each with a set of jobs, compete to perform their respective jobs on a common processing resource. Each agent wants to minimize the total completion times of its jobs only and, associated with one agent's objective value, a certain utility can be derived for each agent. On the other hand, we adopt as an index of collective satisfaction (system utility) the sum of the agents' utilities. A system optimum is any solution maximizing system utility. However, such a solution may well be highly unbalanced and therefore possibly unacceptable by the worse-off agent. Hence, we are interested in a solution that incorporates some criterion of equity for the agents and, to this purpose, we make use of a concept of fairness-namely the Kalai-Smorodinsky solution-which is standard in game theory. We propose different MIP models and a heuristic algorithm to tackle the problem of determining a schedule which is fair to both agents. These approaches are then tested to assess their performance. Finally, an empirical evaluation of the amount of system utility that must be traded to reach a fair solution is given.
Disciplines :
Production, distribution & supply chain management
Author, co-author :
COSMI, Matteo ; University of Luxembourg > Faculty of Law, Economics and Finance (FDEF) > Department of Economics and Management (DEM) > LCL ; Luxembourg Centre for Logistics and Supply Chain Management, Luxembourg
Nicosia, Gaia; Dipartimento di Ingegneria, Università degli Studi Roma Tre, Rome, Italy
Pacifici, Andrea; Dipartimento di Ingegneria Civile e Ingegneria Informatica, Università degli Studi di Roma Tor Vergata, Rome, Italy
External co-authors :
yes
Language :
English
Title :
Computing Fair Solutions in Single Machine Scheduling
Agnetis, A., Chen, B., Nicosia, G., and Pacifici, A. (2019). Price of fairness in two-agent single-machine scheduling problems. European Journal of Operational Research, 276(1), 79-87.
Agnetis, A., Kellerer, H., Nicosia, G., and Pacifici, A. (2012). Parallel dedicated machines scheduling with chain precedence constraints. European Journal of Operational Research, 221(2), 296-305.
Agnetis, A., Nicosia, G., Pacifici, A., and Pferschy, U. (2013). Two agents competing for a shared machine. Lecture Notes in Computer Science, 8176 LNAI, 1-14.
Agnetis, A., Nicosia, G., Pacifici, A., and Pferschy, U. (2015). Scheduling two agent task chains with a central selection mechanism. Journal of Scheduling, 18(3), 243-261.
Artigues, C., Koné, O., Lopez, P., and Mongeau, M. (2015). Mixed-integer linear programming formulations. In C. Schwindt and J. Zimmermann (eds.), Handbook on Project Management and Scheduling Vol.1, 17-41. Springer International Publishing.
Bertsimas, D., Farias, V., and Trichakis, N. (2011). The price of fairness. Operations Research, 59(1), 17-31.
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., and Kyropoulou, M. (2009). The efficiency of fair division. In 5th International Workshop on Internet and Network Economics, WINE 2009, volume 5929 LNCS, 475-482. Springer.
De Cicco, L., Manfredi, G., Palmisano, V., and Mascolo, S. (2020). A multi-commodity flow problem for fair resource allocation in multi-path video delivery networks. IFAC-PapersOnLine, 53(2), 7386-7391.
Dunning, I., Huchette, J., and Lubin, M. (2017). Jump: A modeling language for mathematical optimization. SIAM Review, 59(2), 295-320.
Ertogral, K. and Wu, D.S. (2000). Auction-theoretic coordination of production planning in the supply chain. IIE Transactions, 32(10), 931-940.
Haitao Cui, T., Raju, J.S., and Zhang, Z.J. (2007). Fairness and channel coordination. Management Science, 53(8), 1303-1314.
Jiang, Y., Wu, X., Chen, B., and Hu, Q. (2021). Rawlsian fairness in push and pull supply chains. European Journal of Operational Research, 291(1), 194-205.
Józefowski, L., Józefowska, J., and Kubiak, W. (2009). Fairness of schedules in the control of packet-switched networks. IFAC Proceedings Volumes, 42(13), 220-223.
Kalai, E. and Smorodinsky, M. (1975). Other Solutions to Nash's Bargaining Problem. Econometrica, 43(3), 513-518.
Karsu, O. and Morton, A. (2015). Inequity averse optimization in operational research. European Journal of Operational Research, 245(2), 343-359.
Lang, F. and Fink, A. (2015). Collaborative machine scheduling: Challenges of individually optimizing behavior. Concurrency and Computation: Practice and Experience, 27(11), 2869-2888.
Naldi, M., Nicosia, G., Pacifici, A., and Pferschy, U. (2019). Profit-fairness trade-off in project selection. Socio-Economic Planning Sciences, 67, 133-146.
Nicosia, G., Pacifici, A., and Pferschy, U. (2017). Price of fairness for allocating a bounded resource. European Journal of Operational Research, 257(3), 933-943.
Zhang, Y., Zhang, Z., and Liu, Z. (2020). The price of fairness for a two-agent scheduling game minimizing total completion time. Journal of Combinatorial Optimization. doi:10.1007/s10878-020-00581-5.
