 American Journal of Operations Research, 2013, 3, 439-443 http://dx.doi.org/10.4236/ajor.2013.35042 Published Online September 2013 (http://www.scirp.org/journal/ajor) Scheduling Jobs with a Common Due Date via Cooperative Game Theory Irinel Dragan University of Texas at Arlington, Mathematics, Arlington, USA Email: dragan@uta.edu Received October 18, 2012; revised December 30, 2012; accepted January 7, 2013 Copyright © 2013 Irinel Dragan. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. 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 d ate. A four person game illustrates the basic ideas and the co mpu- tational difficulties. Keywords: Schedule; Efficient Value; Egalitarian Value; Eg alitarian Nonseparable Contribution; Shapley Value; Cost Excesses; Lexicographic Ordering; Cost Least Square Prenucleolus 1. A Scheduling Game and Simple Solutions A machine may process jobs, 12 n n ,,,,JJ with the completion times 12 all positive numbers. No two jobs can be simultaneously done, and for all jobs there is a common due date positive. Any schedule ,,,, n pp p d is a sequence of jobs, and no preemption is allowed. The schedule is determined by the numbers ,,CiN i the completion dates of the jobs i in . Any deviation from the due date will be penalized, either an early or a late completion relative to the due date. The total time deviation in a schedule is given by . (1) i iN Cd * The usual scheduling problem is to: find out the schedule for which the total deviation is minimal. In [1], J. J. Kanet solved the problem for the case when the sum of completion times is smaller than, or equal to and gave an algorithm for computing a schedule with a minimal deviation. Of course, this algorithm may be used to find the total penalty for this schedule and also to find the total penalty for any minimal deviation corre- sponding to any subset of jobs. This makes sense in the case when the costs of the deviations, early or late, are proportional to their size. In the following, we assume that the costs are equal to the penalties. A more general case other than Kanet’s has been solved by M. U. Ahmed and P. S. Sundararaghavan in [2]. In [3], N. G. Hall and M. E. Posner consider similar problems. The literature connected to more general cases is huge, and the conclu- sions obtained in the present paper can be applied to most other cases. For the present discussion, the simplest case offered by Kanet’s algorithm, with the above as- sumptions, is good enough to suggest similar appro aches in all other cases, in connection with a new problem to be introduced below. Assuming that the grand coalition has been formed and the total penalty for early and late deviation, ,wN has been computed by some algorithm, a new problem is: how much should be a fair individual penalty for each job? To answer the question, we now build the following cooperative game with transferable utilities: let 1, 2,,Nni , i be the set of players, the player be for each the customer ordering the job 1, 2,,in ,,,SS NS ,Si ,dp Consider any coalition of customers, and notice that if then the ,dminimal schedule starts the co rresponding job at i and there will be no deviation from the due date. There- fore, if we denote the deviation for coalition by ,S 0.wi ,wS we have An algorithm for compu- ting the minimal deviation, for example Kanet’s algo- rithm, will provide the total deviation when 0,wS 2.S In this way, we get a cooperative TU game ,,Nw .wN in which we want to divid e fai rl y To make the paper self contained let us sketch Kanet’s algorithm which will be used in the example shown be- C opyright © 2013 SciRes. AJOR  I. DRAGAN 440 low. Let be any coalition and denote by S (be- fore ), a sequence of jobs which were already selected, with non-increasing processing times and the last job ending at also, denote by S,B S ;d, S (after ), another sequence of jobs which were already selected, with non- decreasing processing times and starting at Now, assume that we have S .d ,,B AS SSS S Kanet’s algorithm is continuing to build the partition of as follows: if BA 1,S ,B SS BA select the non-selected element of with a maximal processing time and take it as the last job in (now we have S S 1BA SS ,B). Further, if with the new Swe have 1,BAS S, SS then choose the non-selected job in with a maximal processing time and take it as the first job in S (that is starting at ). Repeat the pro- cedure, selecting alternatively players in S then in S d,B , until is exhausted; then, the time deviation is computed by formula (1) for the corresponding schedule and in the same way for any subset of players. S ,,, Example 1: Let 1234 JJJ 8, 5,p 1, 2,3, 4N be a set of jobs to be processed on a single machine, with the processing times and the due date is 12 12, 10,ppp 39, 34 such that the Kanet’s condition shown above holds. We can compute for the set of players d , and its subsets, the total penalties. Ka- net’s algorithm will generate the game 12ww w 340,w 1, 210,1, 3 1, 42, 4 ww ww 2, 38, 3, 45, w w 2,3,4 28.w 28wN 1, 2,318,1, 2, 415, 1,3,42,3,413,1, ww ww This corresponds to the total deviations of all coali- tions, and our problem is to: find out how we should di- vide fairly among the players? We start by showing two simple solutions: the Egalitarian allocation and the Egalitarian non-separable contribution allocation. Denoting the first by *, we get 7,7,7,7 .*x *,y Denoting the second by which is given in gen- eral by formula * 1 i jN ywNwNi wNwN wNj n ,, i N ,, (2) we get the marginal contributions j wN wN jjN equal to 15, 15, 13, 10, so that the sum makes 53, and from each marginal contribution we should subtract 25/4, to obtain 35 *,y Looking at the characteristic values of our game, shown in example 1, we see that the players 1 and 2 seem to be equal, while players 3 and 4 are weaker, hence the last two should be asked to pay smaller individual penal- ties. The first solution does not seem to show this, while the second seems more fair, we shall see a method below to compare the fairness of the solutions. 2. Individual Penalties: Set Solutions, Shapley Value 3527 15 ,,. 4444 ,z ,,,SS NS ,z To evaluate the fairness of a possible solution we may use the excess functions; however, here it seems more appropriate to use some similar functions that we shall call the “cost excess” functions. For any coalition and any allocation the cost excess function is ,. i iS Szz wS (3) These are the negatives of usual excess functions, ob- viously, we have 22 n such functions, because for the grand coalition, for any allocation, by definition we have ,0.Nz In words, the cost excess is the difference between what the coalition will pay in to contri- bute as close as possible to the total penalty for herself, while it is also contributing to the total penalty for Then, what we want to do is to choose the allocation which minimizes all cost excesses on the set of alloca- tions. Note that the sum of all cost excesses is a constant, because for any allocation we have S z .N z z 1 ,2 . n SN SN SzwN wS (4) Moreover, we can define the average cost excess 1,, 21 nSN wSz z (5) which by formula (4) does not depend on the allocation This means that if the allocation of some coalition is increased, then the allocation of at least one other coali- tion will be decreased. How the cost excesses are used to compare the fairness of two allocations is illustrated be- low. Example 2: Return to example 1, and write the cost ,,Nw and any allocation excesses for that game 12 34 1,, 2,, 3,, 4,, zz zz zz zz 12 13 1, 2,10, 1, 3,8, zzz zzz Copyright © 2013 SciRes. AJOR  I. DRAGAN 441 14 24 1,4,5,2,3 , 2,4 ,5,3,4, zzz z zzz z 23 34 8, 5, zz zz 13 124 218 , 15, zz zz 134 234 13, 13. zz zz ,6,6,6,4,3. 4. 1, 2,3, 1, 2,4, zz zz 1, 3,4, 2,3,4, zz zz Our problem is to minimize all cost excesses, while we are on the set of allocations, that is the efficiency condi- tion holds. In other words, we want to minimize the maximal cost excess, subject to efficiency condition, or to use another method to solve a multi objective linear programm i ng pr o blem. Let us try to evaluate the fairness of the two alloca- tions offered until now. For the Egalitarian solution, we can compute the cost excesses and put them in a vector of non increasing ex- cesses, which may be called the vector of unhappiness, as the components are taken in the order of non increasing unhappiness * 9,9,9,8,8,7,7,7,7x It follows that the most unhappy coalitions are the two person coalitions in which one of the players is player For the Egalitarian non separable contribution, we find the vector of unhappiness * 353515 1515151527252525 ,,,,,,,,,, 44222224444 y 2511 15 ,,,, 4 24 1 and the most unhappy coalitions are and 2. Moreover, we have also * 1 larger than 1*, that is the most unhappy coalition in * is more un- happy than the most unhappy coalition in We can say that is better than *.y *.y*, or more fair. Note that the same thing could be said if some pairs of corre- sponding comp onents in the two unhappiness vectors are equal, but the first one which is different is smaller in * than in *. In this case, we also write * L*, x where means the lexicographic L order, and read is better than *y*. Until now, we have seen two simple solutions belonging to Game Theo- ry, they are one point solutions because each one is pro- viding a unique solution. One of the set solutions from Game Theory is the CORE, which for a cost game like ours is the ,Nw , .NS 4.n set , :,0,,0, n CON w zR NzSzS (6) Any element of the CORE is considered as a good al- location, because such an allocation covers the total pe- nalty for each coalition. Looking at the two simple solu- tions of example 1, which as seen in example 2 have all excesses non negative, we see that both are in the CORE, but, of course, there are others with the same property. Moreover, we can also see that the sum of excesses equals 96, that is the worth obtained in formula (4) for The most famous one point solution, which may also be in the CORE, is the Shapley Value, introduced in [4], and defined by a set of axioms, describing some basic properties requir ed for a fair solution. The Shapley Value was proved there to be given by the formula : , 1! !,. ! i Si S SHNw sns vSvSii N n (7) Example 3: For the game consider ed in ex ample 1 , we get ,8,8,7,5.SHN w Computing the cost excesses and ordering them, we obtain 8,8,8,8,7,7,7,7,7,7,6,6,5,5 .SH We get **, LL SH yx 2 Minimize ,,, SN fwzSzw because the first components of the unhappiness vectors are in this order, hence the Shapley Value is better than the Egalitarian non separable contribution, which is better than the Ega- litarian solution. Note that this may not be the case for other games. Note also that if the game is large, then the Shapley Value may not be easy to compute. An algo- rithm based upon the so called Average per capita for- mula, given by the author in [5], may be used, as it will be explained in the next section and the algorithm is al- lowing even a parallel computation of the Shapley Value. Similar situations may occur in connection with the other values. 3. The Cost Least Square Prenucleolus In the following, we may consider as a solution the Least Square Prenucleolus of the game, introduced by L. Ruiz, F. Valenciano and J. Zarzuelo in [6]. This is similar to the Prenucleolus, introduced in connection with the Nu- cleolus, due to D. Schmeidler [7], except that this was defined by means of the following quadratic program- ming problem (8) subject to ,0.Nz (9) Copyright © 2013 SciRes. AJOR  I. DRAGAN Copyright © 2013 SciRes. AJOR 442 By using the Kuhn-Tucker conditions, in (8), (9), it has been shown that our problem has a unique solution, that the authors called the Least Square Prenucleolus, namely to other scheduling problems in which the associated scheduling game can still be generated by some algo- rithm. Some of the following remarks may help: 1 , ii jN wN LSN wnawa nn , , j wi N 1 :1 2. 1 n s n s (10) where ,, iSi S aw wSi N (11) As the cost excesses are replacing the excesses, we called this value the Cost Least Square Prenucleolus, but the expressions (10) and (11) are the same even in our case. Example 4: Computing by (10) and (11) this solution for our game , we get 129 1 ,, 16 LSN w29 11377 ,,. 1616 16 *LS **, LLL y x The vector of unhappiness is (see foot-note). Notice that the sum of cost excesses is also 96. Now, checking the comparison of the new solution with the other three solutions, we obtain ,,SHNwLSNw that is the Shapley Value seems to be more fair than the other three values. Of course, the Schmeidler’s Prenu- cleolus may also be computed; the computational method, due to A. Kopelowitz [8], is also shown in [9]. However, this includes a long computation for solving a sequence of linear optimization problems. The Prenucleolus would be the best, by the definition of the value. Another princip le may be used to choose the appr opri- ate allocation: for each allocation available, compute the difference between the cost for the most unhappy coali- tion and the happiest coalition and choose the allocation that gives the smallest difference. Such an allocation would not give a high difference of costs between the happy and the unhappy coalitions. In our case, we have ** 5, 6. x dd 5n 129 77 13 3, , 16 164 SH LSy dd 1) The above discussion was illustr ated by examples 1 , 2, 3, 4 relative to a four person game. If we have jobs, under the same conditions like above, Kanet’s algo- rithm still applies when the Kanet’s assumption holds. If the objective is different, for example to minimize a weighted combination of deviations relative to a comm on due date, then the algorithm by Hall and Posner should be used to get the scheduling game. 2) As soon as the game is available, the problem of di- viding fairly the worth of the grand coalition is the prob- lem of choosing an efficient value from Game Theory, for which the computation could be done. As all single- tons have a zero worth, the Center of the imputation set [9] becomes the Egalitarian value, which in general is not fair. The Egalitarian non-separable contribution may be an alternative allocation. The Shapley Value, which has a lot of properties derived from the axioms, is the most preferred by almost all scientists, but for more than ten players it becomes difficult to compute. For such large games it may be better to use the formula given by the author in [5], called the Average per capita form ula Notice that by the last principle the four values are or- dered in the same way. 4. Conclusions The technology put together in the present paper applies 1 ,,, i sn ss is ww SHN wiN s (12) where w, is the average worth of coalitions of size and i w, is the average worth of coalitions of size that do not contain player with n It is obvious that the task can be performed by teams, and each one computes one ratio for one ,i0, . i wiN n . 3) In the computation of the Cost Nucleolus by Ko- pelowitz’ method [8,9] the passage from one LP prob- lem to the next is not described in details in most sources. The complementary conditions show which cost excesses should remain constant on all optimal solutions of the current problem, and should be kept constant in the next problem. These equations should replace the correspon- ding inequalities of the current problem and remain satis- fied until we meet a problem which has a unique solution. The solution of the quadratic programming problem seems easier to compute. The generalized nucleolus may be used as a solution of any Multicriteria Linear Programming problem, as shown by the author in [10], working with a three person game. The basic idea appeared in a former paper of the author [11], as well as in the more recent paper by E. Marchi and J. A. Oviedo [12]. 129129 636357 5711311111155 49958377 *,,,,,,,, ,,,,,. 161688881616168816 1616 LS  I. DRAGAN 443 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 Penal- ties 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 Sche- duling Problems, I: Weighted Deviation of the Comple- tion Times about a Common Due Date,” Operations Re- search, 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 Func- tion 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 Appli- cation to a Traffic Problem,” Quaderni dei Gruppi di Ricerca CNR, Pisa, 1981 [12] E. Marchi a n d J. A. Oviedo, “Lexicogra p hic Optimality in the Multiple Objective Linear Programming: The Nucleo- lar Solution,” European Journal of Operational Research, Vol. 57, No. 3, 1992, pp. 353-359. doi:10.1016/0377-2217(92)90347-C Copyright © 2013 SciRes. AJOR
|
