# Multiple-Machine Scheduling with Learning Effects and Cooperative Games

Authors: Yiyuan Zhou; Qiang Zhang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Multiple-machine scheduling problems with position-based learning effects are studied in this paper. There is an initial schedule in this scheduling problem. The optimal schedule minimizes the sum of the weighted completion times; the difference between the initial total weighted completion time and the minimal total weighted completion time is the cost savings. A multiple-machine sequencing game is introduced to allocate the cost savings. The game is balanced if the normal processing times of jobs that are on the same machine are equal and an equal number of jobs are scheduled on each machine initially.


---

## Body

## 1. Introduction

In a single-machine scheduling problem, a finite number of jobs are processed on a machine. Jobs are characterized by normal processing times, weights, due-dates, release times, and so on. The objective is to minimize a given function, such as the sum of the completion times, the sum of the weighted completion times, the maximal lateness, and the makespan.Scheduling problems with learning effects were first introduced by Biskup [1], who described the actual processing time of a job as a decreasing power function of its position. Since then, several classes of learning effects in scheduling problems have been studied, namely, time-dependent learning effects [2–6], position-based learning effects [7–13], combined effects of position-based effects and time-dependent effects [14–17]. In a scheduling problem with time-dependent learning effects, the actual processing time of a job depends on the total processing times of jobs already processed, while, in a scheduling problem with position-based learning effects, the actual processing time of a job is a function of its position. In a scheduling problem with learning effects, the later a job starts, the shorter its actual processing time is. Learning effects have also been introduced to multiple-machine scheduling problems [8–10, 12, 15]. The main aims of the above works are optimal schedules, algorithms, and complexities of the algorithms. We refer to [18] for a review of scheduling with learning effects.Cooperative games arising from scheduling or sequencing situations are called sequencing games. Curiel et al. [19] considered a single-machine sequencing situation, in which each job belongs to an agent (a player) and there is an initial order of jobs. The weight of a job is the cost per unit time of the agent. The optimal order minimizes the total cost which is the sum of the weighted completion times. The difference between the initial total cost and the minimal total cost can be seen as cost savings of all agents. This begs the question: How to allocate the cost savings among the agents fairly? Curiel et al. tackled this problem by introducing sequencing games. Sequencing games have been extended by many researchers. The extensions focus on the allocation rules [20, 21], the number of jobs [22, 23], the admissible rearrangements of jobs [24, 25], the initial order of jobs [26, 27], the family or batch sequencing situations [28, 29], the ready times [30], and the due-dates [31]. Convexity and balancedness of the corresponding sequencing games are the main goals of these studies as convex games and balanced games have nice properties.Studies on the sequencing games with multiple machines are also found in the literatures. Hamers et al. [32] and Slikker [33] proposed a multiple-machine scheduling in which each player has one job and each job is processed on one machine only; the corresponding sequencing game is balanced if the normal processing times are equal or the weights are equal. Calleja et al. [34] considered a two-machine scheduling in which each player has two jobs and each job must be processed on each machine; it is shown that the corresponding sequencing game is balanced. Slikker [35] extended the model in [34] to sequencing games with m machines and n jobs.In all the above mentioned models, the processing times are constant. van Velzen [36] studied a sequencing game with controllable processing times, where the processing times can be reduced to crashed processing times; the corresponding sequencing games are balanced but need not be convex.In this paper, a multiple-machine scheduling problem with position-based learning effects is studied. In our model, each player has one job to be processed on one machine only, there is an initial schedule of the jobs, and the learning index depends on the machine. The actual processing time of a job is not a constant but a power function of its position. To achieve the optimal schedule, the jobs should be rearranged, and a rearrangement results in some changes of the processing times. The processing time of a job decreases if the job moves to the back of its queue; it increases if the job moves to the front of its queue. A multiple-machine sequencing game is introduced to allocate the cost savings. The game is balanced if and only if a related machine game is balanced. If in the initial schedule the normal processing times of jobs that are on the same machine are equal and each machine has an equal number of jobs, then the related machine game is balanced; furthermore, the multiple-machine sequencing game is balanced. To the best of our understanding, sequencing games have not been studied so far.The rest of the paper is organized as follows. In Section2 some preliminaries are recalled. In Section 3 a multiple-machine scheduling problem with learning effects is considered, and a cooperative game is defined on this scheduling problem. In Section 4 it is shown that a simple multiple-machine sequencing game with learning effects is balanced. Some concluding remarks are given in Section 5.


## 2. Preliminaries

A cooperative game is denoted by(N,v), where N={1,2,…,n} is the set of players and v:2N→R is the characteristic function such that v(∅)=0.Let(N,v) be a cooperative game and σ an order of the players. A coalition S⊆N is connected if for all i, j∈S and l∈N with σ(i)<σ(l)<σ(j) it holds that l∈S. The game (N,v) is a σ-component additive game if(1)
v({i})=0 for all i∈N,(2)
v(S)+v(T)≤v(S∪T) for all S,T⊆N with S∩T=∅; that is, (N,v) is superadditive,(3)
v(S)=∑T∈S∖σv(T) for all S⊆N, where S∖σ is the set of maximally connected components of S with respect to σ. A coalition T⊆S is maximally connected if T is connected and T∪{i} is not connected for all i∈S∖T.The coreC(v) of a cooperative game (N,v) is defined by(1)Cv=x∈Rn∣xN=vN,xS≥vS∀S⊆N,where x(S)=∑i∈Sxi.For a cooperative game(N,v) and a coalition S⊆N∖{∅}, the subgame (S,v|S) is defined by v|S(T)=v(T) for all T⊆S.LetZ=(zij)n×n be a matrix. A permutation game (N,u) is defined by(2)uS=max⁡π∈ΠS⁡∑i∈Szii-ziπifor all S⊆N, where zij∈Z and Π(S) is the set of all permutations of S.It is well known that the component additive games and the permutation games are balanced [37, 38]; thus their cores are not empty.


## 3. Multiple-Machine Scheduling with Learning Effects and Sequencing Games

In a multiple-machine scheduling problem, there arem machines and n players. Each player has one job to be processed on one of the machines, every job can be processed by any machine, and there is an initial schedule of jobs. Let M={1,2,…,m} denote the set of machines and let N={1,2,…,n} denote the set of players. With an abuse of notation we denote the job of player i by i itself. The normal processing time of job i is denoted by pi≥0. The cost ci of player i depends linearly on the completion time of his job; that is, ci(t)=wit, where wi≥0 is the weight of job i. The objective is to minimize the total cost which is the sum of the weighted completion times of the n jobs.The initial schedule of jobs is denoted byb0:N→M×N, and b0(i)=(k,r) indicates that job i is processed in position r on machine k. The notation b0-1 is the inverse mapping of b0.We assume that all the machines have position-based learning effects. The learning index of machinek is denoted by ak, where ak≤0. Let pirk be the actual processing time of job i if it is scheduled in position r on machine k; then(3)pirk=pirak.A multiple-machine scheduling with learning effects as described above is denoted by(M,N,b0,p,w,a), where vectors p=(pi)i∈N, w=(wi)i∈N, and a=(ak)k∈M.The ordering≺ on M×N is defined as follows. For i, j∈N, b0(j)≺b0(i) if and only if b10(j)=b10(i) and b20(j)<b20(i). It indicates that jobs i and j are on the same machine and i follows j. Note that b10(i) and b20(i) are the first component and the second component of b0(i), respectively. Let P(b0,i)={j∈N∣b0(j)≺b0(i)} and F(b0,i)={j∈N∣b0(j)≻b0(i)}.For eachk∈M, the set Nk(b0)={j∈N∣b10(j)=k} represents the jobs that are on machine k with respect to b0, and nk(b0) is the number of jobs on machine k; that is, nk(b0)=|Nk(b0)|. In addition, σk0:Nk(b0)→{1,2,…,nk(b0)} denotes the initial processing order of the jobs that are on machine k; that is, σk0(i)=r implies that job i is in position r on machine k.Suppose that jobi is on machine k; then the starting time t(b0,i) of job i with respect to b0 is given by(4)tb0,i=∑j∈Pb0,ipjb20jak,and the completion time T(b0,i) of job i is the sum of its processing time and the waiting time; that is,(5)Tb0,i=pib20iak+∑j∈Pb0,ipjb20jak.We assume that, in the initial schedule, the starting time of the last job of each machine is less than or equal to the completion times of the last jobs of other machines. Formally, for eachk∈M, the initial schedule b0 satisfies (6)tb0,lk≤Tb0,lhfor all h∈M, where lk is the last job of machine k with respect to b0. This assumption implies that in the initial schedule the last job of a machine cannot make any profit by joining the end of a queue of any other machine.The cost of jobi with respect to schedule b0 is denoted by C(b0,i). For each coalition S⊆N, the total cost of S is the sum of the costs of jobs contained in S; that is,(7)Cb0,S=∑i∈SCb0,i=∑i∈SwiTb0,i.Clearly, there is an optimal schedule b∗ such that the total cost C(b∗,N) is minimal. The maximal cost savings C(b0,N)-C(b∗,N) can be seen as a profit of all players.The maximal cost savings of a coalitionS depend on the set of admissible schedules of this coalition. A schedule b:N→M×N is admissible for S with respect to b0 if it satisfies the following conditions.(1)
Fori,j∈S, jobs i and j which are on the same machine can be switched only if the jobs that are between i and j belong to S.(2)
Fori,j∈S, jobs i and j that are on different machines can be switched only if both the jobs in F(b0,i) and the jobs in F(b0,j) are contained in S.∑1The set of all admissible schedules for S is denoted by A(S).For multiple-machine scheduling problems with learning effects(M,N,b0,p,w,a), a corresponding m-sequencing game (N,v) is defined by(8)vS=max⁡b∈AS⁡Cb0,S-Cb,S=Cb0,S-CbS∗,S,where bS∗ is the optimal schedule for coalition S. Obviously, v({i})=0 for all i∈N.Remark 1.
LetS⊆Nk(b0) and the last job lk∈S. To achieve the optimal schedule bS∗, the queue of machine k should be rearranged. After the rearrangement, the last job l-k (it may be different from lk) can make a profit by joining the end of a queue of another machine, although this will not occur in the initial schedule. The reason is that the starting time of the last job l-k of the new queue may increase. The following example illustrates this.Example 2.
Let(M,N,b0,p,w,a) be a two-machine scheduling problem with learning effects, where M={1,2}, N={1,2,3}, p=(1,3,2), w=(1,3,20), and a=(-0.2,-0.3). The initial schedule b0 is b0(1)=(1,1), b0(2)=(1,2), and b0(3)=(2,1); it satisfies t(b0,2)<T(b0,3) and t(b0,3)<T(b0,2). Consider the coalition S={1,2}; we have C(b0,S)=11.8350.
Scheduleb1 is given by b1(1)=(1,2), b1(2)=(1,1), and b1(3)=(2,1); thus C(b1,S)=12.8706.
Scheduleb2 is b2(1)=(2,2), b2(2)=(1,1), and b2(3)=(2,1); then C(b2,S)=11.8123. The schedules b0, b1, and b2 are depicted in Figure 1. Obviously, the optimal schedule for {1,2} is b2. The cost C(b0,S) increases if the initial schedule is changed to b1, but there is a profit if the last job of machine 1 in schedule b1 joins the end of the queue of machine 2.Figure 1
The schedules ofb0, b1, and b2.


## 4. Balancedness of Simplem-Sequencing Games with Learning Effects

In this section, we restrict attention to simple multiple-machine scheduling problem with learning effects. A multiple-machine scheduling problem with learning effects is simple if the normal processing times of the jobs that are on the same machine are equal and an equal number of jobs are scheduled on each machine initially. Without loss of generality, we assume that, for allk∈M, nk(b0)=q and pi=λk if i∈Nk(b0). The set of such simple multiple-machine scheduling problems is denoted by SMSλ,q.If jobi is in position r on machinek, then the actual processing time of job i is λkrak, the starting time is λk∑j=1r-1jak, and the completion time, denoted by T(b,i), is given by(9)Tb,i=λk∑j=1rjak.For eachK⊆M, let SK=∪k∈KNk(b0) and let bS(K)∗ denote the optimal schedule for coalition S(K).Lemma 3.
If(M,N,b0,p,w,a)∈SMSλ,q, then nk(bS(K)∗)=q for all k∈K.Proof.
In the initial scheduleb0, the starting time of the last job lk of machine k is λk∑j=1q-1jak, and the completion time of the last job ls of machine s is λs∑j=1qjas since each machine has q jobs. According to assumption (6), we have λk∑r=1q-1rak≤λs∑r=1qras for all s∈M.
In the following, we will show that there is a contradiction ifnk(bS(K)∗)≠q.
Assume thatnk(bS(K)∗)<q. Then there is a machine h∈M such that nh(bS(K)∗)≥q+1. According to the admissible rearrangement, the last job lh∗ of machine h with respect to bS(K)∗ is in coalition S(K). In bS(K)∗, the completion time T(bS(K)∗,lk∗) of the last job lk∗ of machine k satisfies T(bS(K)∗,lk∗)≤λk∑r=1q-1rak since machine k has at most q-1 jobs, and the starting time t(bS(K)∗,lh∗) of the last job lh∗ of machine h satisfies t(bS(K)∗,lh∗)≥λh∑r=1qrah as machine h has at least q+1 jobs. If lh∗ joins the end of the queue of machine k, the cost of lh∗ will decrease since t(bS(K)∗,lh∗)≥λh∑r=1qrah≥λk∑r=1q-1rak≥T(bS(K)∗,lk∗); furthermore, the cost C(bS(K)∗,S(K)) will decrease. It is contrary to the fact that C(bS(K)∗,S(K)) is minimal.
Thusnk(bS(K)∗)=q for all k∈K.Lemma 4.
Let(M,N,b0,p,w,a)∈SMSλ,q and let (N,v) be the corresponding m-sequencing game. Then, for each k∈M, the subgame Nk(b0),v|Nk(b0) is a σk0-component additive game.Proof.
Obviously,Nk(b0),v|Nk(b0) is superadditive, and v|Nk(b0)({i})=0 for all i∈Nk(b0). It is necessary to prove that v|Nk(b0)(S)=∑T∈S∖σk0v|Nk(b0)(T).
It follows from Lemma3 that, in the optimal schedule bNk(b0)∗, the jobs in Nk(b0) are not allowed to join the ends of other queues; thus Nk(b0)=NkbNK(b0)∗ and the subgame Nk(b0),v|Nk(b0) is a single-machine sequencing game.
For eachi∈Nk(b0), the cost of job i with respect to σk0 is denoted by C(σk0,i) and is given by C(σk0,i)=wiT(σk0,i). Following from (9), it holds that(10)Cσk0,i=wiλk∑r=1σk0irak.For any coalition S⊆Nk(b0), (11)vNkb0S=∑i∈SCσk0,i-Cσk,S∗,i,where σk,S∗ is the optimal order for S.
SupposeS∖σk0={T1,T2}; then T1 and T2 are connected, T1∩T2=∅, and T1∪T2 are not connected. The optimal orders of T1 and T2 are denoted by σk,T1∗ and σk,T2∗, respectively. Thus(12)vNkb0S=∑i∈SCσk0,i-Cσk,S∗,i=∑i∈T1Cσk0,i-Cσk,S∗,i+∑i∈T2Cσk0,i-Cσk,S∗,i=∑i∈T1∑r=1σk0iwiλkrak-∑i∈T1∑r=1σk,S∗iwiλkrak+∑i∈T2∑r=1σk0iwiλkrak-∑i∈T2∑r=1σk,S∗iwiλkrak,where the third equality follows from (10). Since jobs in T1 are not allowed to join the coalition T2 and vice versa, we have σk,S∗(i)=σk,T1∗(i) if i∈T1 and σk,S∗(j)=σk,T2∗(j) if j∈T2. Hence(13)vNkb0S=∑i∈T1∑r=1σk0iwiλkrak-∑i∈T1∑r=1σk,T1∗iwiλkrak+∑i∈T2∑r=1σk0iwiλkrak-∑i∈T2∑r=1σk,T2∗iwiλkrak=Cσ0,T1-Cσk,T1∗,T1+Cσ0,T2-Cσk,T2∗,T2=vNkb0T1+vNkb0T2.The proof follows exactly in the same way for S∖σk0={T1,T2,…,Tl}.Remark 5.
The subgameNk(b0),v|Nk(b0) need not be a σk0-component additive game if there is an i∈Nk(b0) such that pi≠λk.Example 6.
LetNk(b0)={1,2,3,4}, p=(3,1,1,1), w=(1,1,5,3), ak=-0.2, and λk=1, and the initial order σk0 is given by σk0(i)=i for all i∈Nk(b0). Take the coalition S={1,2,4} such that S∖σk0={{1,2},{4}}. It follows that(14)vNkb01,2=w1p1+w2p1+p22ak-w2p2-w1p2+p12ak=2.2589,vNkb0S=w1p1+w2p1+p22ak+w4p1+p22ak+p33ak+p44ak-w2p2-w1p2+p12ak-w4p2+p12ak+p33ak+p44ak=3.0356,and v|Nk(b0)({4})=0. Obviously, Nk(b0),v|Nk(b0) is not a σk0-component additive game since vNk(b0)({1,2,4})≠vNk(b0)({1,2})+vNk(b0)({4}).
Although the position of job 4 is unchanged, its completion time decreases if jobs 2 and 3 are switched. In other words, switching of jobs 2 and 3 results in an “extra” profit for job 4.Before we prove the balancedness of the correspondingm-sequencing game, a machine game is defined.Let(M,N,b0,p,w,a)∈SMSλ,q and let (N,v) be the corresponding m-sequencing game. For each K⊆M, a machine game (M,w) is defined by(15)wK=v⋃k∈KNkb0-∑k∈KvNkb0.The machine game (M,w) is defined on the set of machines. The value w(K) is the cost savings that the machines in K can attain if they cooperate.Since subgamesNk(b0),v|Nk(b0) are σk0-component additive games for all k∈M, following Theorem 3.1 in [32] and Theorem 4.1 in [33], we have the following.Theorem 7.
Let(M,N,b0,p,w,a)∈SMSλ,q, and let (N,v) and (M,w) be the corresponding m-sequencing game and machine game, respectively. Then (N,v) is balanced if and only if (M,w) is balanced.The following lemma shows that the coalition valuevS(K) can be rewritten as a value of a permutation game.Lemma 8.
If(M,N,b0,p,w,a)∈SMSλ,q and (N,v) is the corresponding m-sequencing game, then there is a permutation game (N,u) such that(16)vSK=uSKfor each K⊆M.Proof.
For convenience, renumber the machines inK such that K={1,2,…,|K|}. Note that(17)Cb,SK=∑k∈K∑r=1qwb-1k,rλk∑β=1rβak,vSK=max⁡b∈ASK⁡Cb0,SK-Cb,SK=max⁡b∈ASK⁡∑k∈K∑r=1qwb0-1k,rλk∑β=1rβak-∑k∈K∑r=1qwb-1k,rλk∑β=1rβak.For i, j∈{1,2,…,|K|q}, let zij=wiλk∑μ=1j-(k-1)qμak if (k-1)q+1≤j≤kq; then we have(18)wb-1k,rλk∑β=1rβak=zb-1k,r,k-1q+r,vSK=max⁡b∈ASK⁡∑k∈K∑r=1qzb0-1k,r,k-1q+r-∑k∈K∑r=1qzb-1k,r,k-1q+r.For each schedule b∈A(S(K)), there is a permutation πb∈Π(S(K)) such that (19)πbi=b1i-1q+b2ifor all i∈N. For each permutation π∈Π(S(K)), there is a schedule bπ∈A(S(K)) satisfying(20)bπi=k,πi-k-1q,where k is such that (k-1)q+1≤π(i)≤kq. Thus(21)vSK=max⁡b∈ASK⁡∑i∈SKzi,πb0i-∑i∈SKzi,πbi=max⁡π∈ΠSK⁡∑i∈SKzi,i-∑i∈SKzi,πi=uSK,where the first equality follows from (19) and the second equality follows under the assumption πb0i=i.Arising fromS(K)=⋃k∈KNk(b0), we have(22)v⋃k∈KNkb0=u⋃k∈KNkb0.Theorem 9.
If(M,N,b0,p,w,a)∈SMSλ,q, then the corresponding m-sequencing game (N,v) is balanced.Proof.
Following from (22), we have(23)wK=v⋃k∈KNkb0-∑k∈KvNkb0=u⋃k∈KNkb0-∑k∈KvNkb0.Since the permutation game (N,u) is balanced, the core C(u) is not empty, and there is a vector x∈C(u). Let yk=x(Nk(b0))-v(Nk(b0)) for all k∈M; then(24)∑k∈Kyk=∑k∈KxNkb0-∑k∈KvNkb0≥u⋃k∈KNkb0-∑k∈KvNkb0=wK,where the inequality follows from the fact that x is a core element of the game (N,u). If K=M, then ∑k∈Myk=w(M). Thus y∈C(w), the core of the game (M,w) is not empty, and (M,w) is balanced.
The balancedness of them-sequencing game (N,v) follows from Theorem 7 directly.


## 5. Conclusions

Cooperative games based on multiple-machine scheduling problems with learning effects are investigated, where the processing times are not constants. A necessary and sufficient condition for the balancedness of the corresponding sequencing games is that the related machine games are balanced. Furthermore, the sequencing games are balanced if normal processing times of the jobs that are on the same machine are equal and each machine has an equal number of jobs to be processed.If the normal processing times of jobs that are on the same machine are different, then the corresponding subgames which are defined on one machine are not component additive games, and Theorem7 does not hold. The balancedness of general sequencing games with learning effects in which the normal processing times are different will be studied in the future.



---

*Source: 197123-2015-07-27.xml*