Scheduling Jobs with a Common Due Date via Cooperative Game Theory


Efficient values from Game Theory are used, in order to find out a fair allocation for a scheduling game associated with the problem of scheduling jobs with a common due date. A four person game illustrates the basic ideas and the computational difficulties.

Share and Cite:

I. Dragan, "Scheduling Jobs with a Common Due Date via Cooperative Game Theory," American Journal of Operations Research, Vol. 3 No. 5, 2013, pp. 439-443. doi: 10.4236/ajor.2013.35042.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] J. J. Kanet, “Minimizing the Average Deviation of Job Completion Times about a Common Due Date,” Naval Research Logistics Quarterly, Vol. 28, No. 4, 1981, pp. 643-652. doi:10.1002/nav.3800280411
[2] M. U. Ahmed and P. S. Sundararaghavan, “Minimizing the Weighted Sum of Late and Early Completion Penalties in a Single Machine,” IEEE Transactions, Vol. 22, No. 3, 1990, pp. 288-290. doi:10.1080/07408179008964183
[3] N. G. Hall and M. E. Posner, “Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of the Completion Times about a Common Due Date,” Operations Research, Vol. 39, No. 5, 1991, pp. 839-846.
[4] L. S. Shapley, “A Value for n-Person Games,” Annals of Mathematics, Vol. 28, 1953, pp. 307-317.
[5] I. Dragan, “An Average per Capita Formula for the Shapley Value,” Libertas Mathematica, Vol. 12, 1992, pp. 139-146.
[6] L. Ruiz, F. Valenciano and J. Zarzuelo, “The Least Square Prenucleolus and the Least Square Nucleolus, Two Values for TU Games Based on the Excess Vector,” International Journal of Game Theory, Vol. 25, No. 1, 1996, pp. 113-134.
[7] D. Schmeidler, “The Nucleolus of a Characteristic Function Game,” SIAM Journal on Applied Mathematics, Vol. 17, No. 6, 1967, pp. 1163-1170. doi:10.1137/0117107
[8] A. Kopelowitz, “Computation of the Kernels of Simple Games and the Nucleolus of n-Person Game,” RM 31, Hebrew University of Jerusalem, Jerusalem, 1967.
[9] G. Owen, “Game Theory,” 3rd Edition, Academic Press, New York, 1995.
[10] I. Dragan, “A Game Theoretic Approach for Solving Multiobjective Linear Programming Problems,” Libertas Mathematica, Vol. 30, 2010, pp. 149-158.
[11] I. Dragan, “A Game Theoretic Approach for Solving Multiobjective Linear Programming Problems: An Application to a Traffic Problem,” Quaderni dei Gruppi di Ricerca CNR, Pisa, 1981
[12] E. Marchi and J. A. Oviedo, “Lexicographic Optimality in the Multiple Objective Linear Programming: The Nucleolar Solution,” European Journal of Operational Research, Vol. 57, No. 3, 1992, pp. 353-359. doi:10.1016/0377-2217(92)90347-C

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.