# Shapley Value for Parallel Machine Sequencing Situation without Initial Order

Authors: Shanshan Liu; Zhaohui Liu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We consider the parallel identical machine sequencing situation without initial schedule. For the situation with identical job processing time, we design a cost allocation rule which gives the Shapley value of the related sequencing game in polynomial time. For the game with identical job weight, we also present a polynomial time procedure to compute the Shapley value.


---

## Body

## 1. Introduction

We consider them-sequencing situation first introduced by Hamers et al. [1]. There are n players and each owns exactly one job to be processed on m parallel identical machines M1,M2,…,Mm. Each machine can process one job at a time, and each job needs to be processed on only one machine. Job i, owned by player i(1≤i≤n), has a processing time pi and a weight wi. Each player takes the cost of his job which occurred in the processing system. The cost is defined as the weighted completion time. The processing is carried out according to a schedule. In a schedule the jobs are partitioned into m subsets, and each is processed on one of the machines. The processing order on machine Mk(1≤k≤m) is denoted by σk, which is a permutation of the jobs on Mk. A schedule is thus denoted as π={σ1,σ2,…,σm}. Let Ci(π) be the completion time of job i under the schedule π, and Si(π) the start time. Then the cost of job i is wiCi(π)=wiSi(π)+wipi, and the total cost is ∑i=1n‍wiCi(π). There are two kinds of problems: (1) given an initial schedule, the players cooperate to improve it; (2) without any initial schedule, the players cooperate to reach a schedule. For both kinds of problems, a schedule is finally chosen and a payment scheme is designed in order to carry out the schedule. The payment scheme reallocates the total cost, and a player may take a cost larger or smaller than the cost of his job such that he is satisfied. In this paper we mainly focus on the m-sequencing situation without initial schedule.The solution to a sequencing situation must contain a schedule indicating how the processing is carried out, as well as an allocation scheme of the total cost. The two parts are not independent since the schedule decides the total cost to be allocated and the position of each job is an important factor of deciding the cost of the player. Finding an optimal schedule for the parallel machine scheduling problem of minimizing the total weighted completion time is NP-hard even for the two-machine case (see [2]). A natural heuristic (list heuristic) is to first put the jobs into a list and then assign them to the first idle machine one by one. The heuristic is called the WSPT algorithm if the list is formed by the nonincreasing order of the ratios of job weights and processing times. Kawaguchi and Kyan [3] proved that the WSPT algorithm has a performance ratio of 1+2/2. However, the algorithm is optimal for the special cases in which the jobs have identical processing time or identical weight.Curiel et al. [4] first investigated the single machine sequencing situation with an initial schedule. They constructed a cooperative game, and gave a rule which indicates a specific core element of the game. The characteristic function value of a coalition is the maximal cost savings that the coalition can make by rearranging the jobs in the coalition without jumping over the jobs outside the coalition. Subsequently, various cost allocation schemes were presented for this sequencing situation (see [5–7]). Curiel et al. [8, 9] generalized the cost function of each job to an arbitrary nondecreasing function of the completion time. Some researchers investigated single machine sequencing situations with additional constraints on the jobs. Hamers et al. [10], Borm et al. [11], and Hamers et al. [12] imposed ready times, due dates, and chains precedence constraints, respectively, on the jobs. Grundel et al. [13] analyzed the single machine sequencing situation with family setup times, where the jobs within a family have an identical cost function.Hamers et al. [1] first studied the m-sequencing situation and proved the balancedness of the related sequencing game for m∈{1,2}. When m≥3, the balancedness was shown for two special cases: the identical processing time and the identical weight. Slikker [14] revisited their results and showed that the general 3-sequencing game needs not to be balanced.However, in some practical situations, a clear initial schedule is not available. Klijn and Sánchez [15] first considered the sequencing game without initial schedule. In order to estimate the power of each coalition, they introduced two different cost characteristic functions: Ctail(S) and Cpes(S), where Ctail(S) stands for the minimum cost of coalition S when its jobs are processed last; that is, the coalition forms the tail of a sequence, and Cpes(S) stands for the maximum cost of coalition S among all possible sequences which cannot be reduced by cooperations inside S. Under these two characteristic functions, the corresponding sequencing games are both balanced. Mishra and Rangarajan [16] defined the characteristic function c(S) of coalition S as the minimum total weighted completion time when the machine only processes the jobs in S. In this case, the related sequencing game is no longer balanced, but its Shapley value is well formulated.The Shapley value is a prominent cost allocation for a cooperative game (see [17]), but it is hard to compute in general. In this paper, we study the parallel identical machine sequencing situation without initial schedule and design cost allocation rules for the special cases in which the jobs have identical processing time or identical weight. The rules give the Shapley value in polynomial time.The remainder of this paper is organized as follows. Section2 is a preliminary section. In Section 3, we design a cost allocation rule for the m-sequencing situation with identical job processing time which gives the Shapley value in polynomial time. In Section 4, we formulate the Shapley value of the m-sequencing game with identical job weight.


## 2. Preliminaries

Am-sequencing situation without initial schedule can be formulated as (N,M,p,w), where N={1,2,…,n} is the set of players, M={M1,M2,…,Mm} is the set of machines, p=(p1,p2,…,pn) is the vector of processing times, and w=(w1,w2,…,wn) is the vector of weights. Since each player owns exactly one job and each job belongs to exactly one player, we do not distinguish between the jobs and players. Then, N is also the set of jobs. Also, we suppose that the jobs have been numbered in nonincreasing order of the ratios of their weights and processing times.For them-sequencing game with respect to (N,M,p,w), we define the characteristic function c as follows. For any coalition S⊆N, let c(S)=∑i∈S‍wiCi(πS), where πS is the schedule generated by the WSPT algorithm. We denote the resulting sequencing game as (N,c). In this paper we always use this characteristic function for the m-sequencing game; thus with given processing times and weights, a sequencing game can be uniquely defined. Let SVi(N,c) be the Shapley value of player i. Then,(1)SViN,c=∑S⊆N∖i‍S!n-S-1!n!cS∪i-cS,where |S| is the cardinal of coalition S.The Shapley value can also be characterized by a collection of properties or axioms: efficiency, anonymity, dummy player property, and additivity. Efficiency means the costs taken by the players sum up to the total cost incurred, which isc(N). A player is called dummy player if he contributes no cost when joining any coalition. The dummy player property assures that the Shapley value of a dummy player is zero. In the m-sequencing game, if the processing time or weight of some job is zero, then its owner is a dummy player. Anonymity means that the Shapley value is not influenced by the numbering way of the players, and renumbering will not change the value. In the m-sequencing game, if two jobs have the same weight and processing time, then their Shapley values are the same. Additivity means that if the characteristic functions c1, c2, and c3 satisfy c1=c2+c3, then SVi(N,c1)=SVi(N,c2)+SVi(N,c3).In general, it is hard to compute the Shapley value according to the definition. We present a cost allocation rule for them-sequencing situation with identical processing time, which gives the Shapley value for the respective sequencing game in polynomial time. And for the m-sequencing game with identical weight, we also obtain a method to compute the Shapley value in polynomial time.


## 3.m-Sequencing Situation with Identical Processing Time

In this section, we focus on them-sequencing situation with identical processing time. Let pi=p for any i∈N. Consider a job list l=(l(1),l(2),…,l(n)). Note that job i is on the l-1(i)th position of the list. For job i, let P(l,i) be the set of jobs listed before i, and F(l,i) the set of jobs listed after i. Given the job list l, a schedule can be obtained by list heuristic. We define the cost allocation rule f with respect to the job list l such that player i takes the cost(2)fil=wip+∑j∈Fl,i‍ml-1j-1/m+12l-1jl-1j-1×l-1j-1mwjp+2l-1i-ml-1i-1/m+12l-1i×l-1i-1mwip,where wip is the processing cost of job i, l-1(j)-1/mwjp is the waiting cost of job j, and l-1(i)-1/mwip is the waiting cost of job i. Note that in a schedule π, the waiting cost of job i is wiSi(π), while the processing cost wipi is unrelated with π. When l=(1,2,…,n), we have(3)fi=wip+∑j>i‍mj-1/mj-1/m+12jj-1wjp+2i-mi-1/m+12ii-1mwip.Next we prove that formula (3) gives the Shapley value for the m-sequencing situation with identical processing time. First we consider the case with identical processing time and identical weight; that is, pi=p and wi=w for any i∈N.Lemma 1.
For(N,c) related to the m-sequencing situation with pi=p and wi=w for any i∈N, the Shapley value of any player is (2n-mq)(q+1)wp/2n, where q=n-1/m.Proof.
It is easy to see the schedule generated by theWSPT algorithm is an optimal processing order for the scheduling problem. The total cost of this schedule is(4)cN=mwp+m·2wp+⋯+mqwp+n-mqq+1wp=2n-mqq+12wp.Note that all jobs have the same processing time and the same weight. By anonymity property of the Shapley value, each player shares the same cost. Thus, the Shapley value of any player is (2n-mq)(q+1)wp/2n.Lemma 2.
For(N,c) related to the m-sequencing situation with pi=p and wi=w for any i∈N, the cost allocated to any player by rule f is the Shapley value.Proof.
By Lemma1, we need only to prove that fi(l)=(2n-mq)(q+1)wp/2n for any job list l and any job i, where q=n-1/m. Suppose that job i is on the gth position of list l; that is, g=l-1(i). We have (5)fil=wp+∑j>g‍mj-1/m+1j-1/m2jj-1wp+2g-mg-1/m+12gg-1mwp.
Whenmx+1≤j≤m(x+1), it holds that j-1/m=x. Thus, (6)∑mx+1≤j≤mx+1‍mj-1/m+1j-1/m2jj-1=mxx+121mx+1-1-1mx+m1mx-1mx+1+1mx+1-1mx+2+⋯+1mx+1-1-1mx+m=mxx+121mx-1mx+1=12.Let k=g-1/m and q=n-1/m. If n≤m, then j-1/m=0 for g≤j≤n. Thus, fi(l)=wp=(2n-mq)(q+1)wp/2n. If n>m, we have (7)fil=wp+∑g+1≤j≤n‍mj-1/mj-1/m+12jj-1wp+2g-mg-1/m+12gg-1mwp=wp+∑g+1≤j≤mk+1‍mj-1/mj-1/m+12jj-1wp+∑mq+1≤j≤n‍mj-1/mj-1/m+12jj-1wp+∑mk+1+1≤j≤mq‍mj-1/mj-1/m+12jj-1wp+2g-mk+12gkwp=wp+mkk+1wp21g-1mk+1+mqq+1wp21mq-1n+q-k-12wp+2g-mk+12gkwp=wp+mkk+1wp2g-kwp2+q+1wp2-mqq+1wp2n+q-k-12wp+kwp-mk+1kwp2g=wp+qwp-mqq+12nwp=2n-mqq+12nwp.This completes the proof.The following theorem shows that the rulef under the job list (1,2,…,n) generates the Shapley value for the m-sequencing game with identical processing time.Theorem 3.
For(N,c) related to the m-sequencing situation with pi=p for any i∈N, the Shapley value SVi(N,c) of player i is equal to fi.Proof.
We prove the theorem by induction on the number of jobs of them-sequencing situation. By the WSPT algorithm, when n≤m, each machine processes at most one job; that is, there is no waiting cost for any job; thus the Shapley value of player i satisfies SVi(N,c)=wip=fi.
Whenn=m+1, we calculate the Shapley value by its definition. Note that c(S)=∑i∈S‍wip holds for all S⊆N satisfying |S|≤n, and c(N)=∑i∈N‍wip+wnp. We have (8)SViN,c=n-1!n!ci-cϕ+∑k=1n-2‍∑S=k,S⊆N∖i‍k!n-k-1!n!cS∪i-cS+∑S=n-1,S⊆N∖i‍n-1!n!cN-cN∖i=wipn+wip∑k=1n-2‍∑|S|=k,S⊆N∖i‍k!n-k-1!n!+wnp+wipn=wip∑k=0n-1‍∑|S|=k,S⊆N∖i‍k!n-k-1!n!+wnpn=wip+wnpn=fi;that is, the theorem holds for n=m+1 too.
Next we suppose that the conclusion holds for them-sequencing situation with n≥m+1 jobs and consider the situation with n+1 jobs. We first construct two auxiliary sequencing games (N,c1) and (N,c2). Note that the jobs in the original game (N,c) have the same processing time p and the weights w1≥w2≥⋯≥wn+1. We suppose that the jobs in (N,c1) and (N,c2) have also the processing time p. For (N,c1), we let all jobs have the same weight wn+1, and for (N,c2), we let the jobs be of weights w1-wn+1,w2-wn+1,…,wn-wn+1,0. It is easy to verify that c=c1+c2. Then we have SVi(N,c)=SVi(N,c1)+SVi(N,c2) since the Shapley value satisfies the additivity property.
From Lemma2, the Shapley value of (N,c1) can be calculated by formula (3). That is, (9)SViN,c1=wn+1p+∑j>i‍mj-1/mj-1/m+12jj-1wn+1p+2i-mi-1/m+12ii-1mwn+1p.In (N,c2), player n+1 is a dummy player since his job is of zero weight and contributes nothing in any coalition. By the dummy player property, SVn+1(N,c2)=0. Let (N∖{n+1},c2′) stand for the sequencing game in which there are only n players 1,2,…,n and c2′ is the restriction of c2 on N∖{n+1}. For player i(1≤i≤n), the Shapley value in (N,c2) is the same as in (N∖{n+1},c2′). According to the induction hypothesis, we have (10)SViN,c2=wi-wn+1p+∑j>i‍mj-1/mj-1/m+12jj-1wj-wn+1p+2i-mi-1/m+12ii-1mwi-wn+1p,for i=1,2,…,n. Applying the additivity of the Shapley value, we obtain (11)SViN,c=SViN,c1+SViN,c2=wip+∑j>i‍mj-1/mj-1/m+12jj-1wjp+2i-mi-1/m+12ii-1mwip=fi.So the conclusion holds.


## 4.m-Sequencing Situation with Identical Weight

In this section, we consider them-sequencing situation in which all jobs have the same weight w, but their processing times may be different. We denote the sequencing situation as (N,M,p). The WSPT algorithm generates an optimal schedule for this problem. We calculate the Shapley value of the related m-sequencing game by decomposing the game into n games with some dummy players.Lemma 4.
Let(N,M,p), (N,M,p′), and (N,M,p′′) be three m-sequencing situations with the same weight w, and p′=(p1,p1,…,p1), and p′′=(0,p2-p1,p3-p1,…,pn-p1). Then, for the respective sequencing games (N,c), (N,c′), and (N,c′′), one has c=c′+c′′.Proof.
It is easy to see that, according to theWSPT algorithm, the jobs of the same number have the same position for (N,M,p), (N,M,p′), and (N,M,p′′). For any coalition S⊆N, this is also true. Consider a schedule σ produced by the WSPT algorithm. Suppose that job i is processed in the kth position on Mt. Let Pt(σ,i) be the set of jobs processed before i on Mt according to σ. For (N,M,p), (N,M,p′), and (N,M,p′′), we have (12)wCiσ=w∑j∈Ptσ,i‍pj+pi,wCi′σ=kwp1,wCi′′σ=w∑j∈Ptσ,i‍pj′′+pi′′,respectively. Since pj′′=pj-p1 for any j and there are exactly k-1 jobs in Pt(σ,i), we get wCi′(σ)+wCi′′(σ)=wCi(σ). This relation holds for any job i, so c=c′+c′′.By Lemma4, we decompose the m-sequencing game (N,c) into (N,c′) and (N,c′′). Denote (N,c′) as (N,c1). Then we decompose (N,c′′) into (N,c2) and (N,c2′′), where the processing times of the jobs in (N,c2) and (N,c2′′) are given by (0,p2-p1,…,p2-p1) and (0,0,p3-p2,…,pn-p2), respectively. Further, we decompose (N,c2′′) into (N,c3) and (N,c3′′) such that the processing times of the jobs in (N,c3) and (N,c3′′) are (0,0,p3-p2,…,p3-p2) and (0,0,0,p4-p3,…,pn-p3). Repeating the process, we finally decompose (N,c) into (N,c1),(N,c2),…,(N,cn), where the processing times of the jobs in (N,ck)(k=2,3,…,n) are given by (13)0,…,0︸k-1zeros,pk-pk-1,…,pk-pk-1.By Lemma 4, we have c=∑k=1n‍ck. And by the additivity of the Shapley value, we have (14)SViN,c=SViN,c1+SViN,c2+⋯+SViN,cn,for any i. By Lemma 1, we have (15)SViN,c1=2n-mn-1/m2nn-1m+1wp1.For k=2,3,…,n, the first k-1 players in (N,ck) are dummy players, so (16)SViN,ck=0,i≤k-1.Let Nk=N∖{1,…,k-1} and ck′ be the restriction of ck on Nk. It holds that SVi(N,ck)=SVi(Nk,ck′) for i∈Nk. However, the Shapley value of (Nk,ck′) can be calculated by Lemma 1. Thus, we have(17)SViN,ck=SViNk,ck′=2n-k+1-mn-k/m2n-k+1n-km+1×wpk-pk-1,i≥k,and the following theorem holds.Theorem 5.
For(N,c) related to the m-sequencing situation with wi=w for any i∈N, the Shapley value of any player can be computed in polynomial time.


## 5. Conclusions

In this paper, we investigate the parallel identical machine sequencing situation without initial schedule. We characterize the Shapley value for two special cases in which the jobs have identical processing time or identical weight. However, it is difficult to compute the Shapley value for the general problem with characteristic function we defined before.We may study the general problem in the following way: choose a feasible schedule, and reach stable cost allocation under the very schedule. And we can use heuristic algorithms such as genetic algorithm or simulate anneal arithmetic to get a final schedule the players agree to. The procedure of deciding the final schedule and the related cost allocation among the players can be done in succession. With a given schedule we do cost allocation machine by machine, which means players whose jobs are on the same machine share the cost which occurred on the very machine. We can design a genetic algorithm to choose the final schedule among all feasible schedules, and for each feasible schedule its fitness function value is the total cost. The cost allocation on each machine is then just like the classic single machine sequencing game, and a cost allocation for each player can be calculated in polynomial time.



---

*Source: 437403-2015-05-18.xml*