Research ArticleOpen AccessGoogle Scholar indexed
Scheduling Jobs with a Common Due Date via Cooperative Game Theory
University of Texas at Arlington, Mathematics, Arlington, USA
- 1 University of Texas at Arlington, Mathematics, Arlington, USA
American Journal of Operations Research·Volume 03 (2013)·Pages 439–443·Published 18 September 2013·DOI10.4236/ajor.2013.35042
Copy link · social · email
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.
KeywordsScheduleEfficient ValueEgalitarian ValueEgalitarian Nonseparable ContributionShapley ValueCost ExcessesLexicographic OrderingCost Least Square Prenucleolus
- 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
- 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
- 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.
- L. S. Shapley, “A Value for n-Person Games,” Annals of Mathematics, Vol. 28, 1953, pp. 307-317.
- I. Dragan, “An Average per Capita Formula for the Shapley Value,” Libertas Mathematica, Vol. 12, 1992, pp. 139-146.
- 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.
- 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
- A. Kopelowitz, “Computation of the Kernels of Simple Games and the Nucleolus of n-Person Game,” RM 31, Hebrew University of Jerusalem, Jerusalem, 1967.
- G. Owen, “Game Theory,” 3rd Edition, Academic Press, New York, 1995.
- I. Dragan, “A Game Theoretic Approach for Solving Multiobjective Linear Programming Problems,” Libertas Mathematica, Vol. 30, 2010, pp. 149-158.
- 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
- 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