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
J
,,,,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
J
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
J
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
A
(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
A
(that is starting at ). Repeat the pro-
cedure, selecting alternatively players in S then in
S
d,B
,
A
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
J
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 *,
x
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
M
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
x
larger than
1*,
y
that is the most unhappy coalition in *
x
is more un-
happy than the most unhappy coalition in We can
say that is better than *.y
*.y*,
x
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

*
y
than in
*.
x
In this case, we also write
*
L*,
y
x

where means the lexicographic L
order, and read is better than
*y*.
x
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
s
w,
is the average worth of coalitions of size
s
and i
s
w,
is the average worth of coalitions of size
s
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
.
s
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