Scheduling Jobs with a Common Due Date via Cooperative Game Theory

Author(s)
Irinel Dragan

ABSTRACT

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.

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.

Cite this paper

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.

I. Dragan, "Scheduling Jobs with a Common Due Date via Cooperative Game Theory,"

References

[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

[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