# Single Machine Group Scheduling with Position Dependent Processing Times and Ready Times

Authors: Xingong Zhang; Qiulian Xie
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We investigate a single machine group scheduling problem with position
dependent processing times and ready times. The actual processing time of a job is a function of positive
group-dependent job-independent positional factors. The actual setup time of the group is a linear
function of the total completion time of the former group. Each job has a release time. The decision
should be taken regarding possible sequences of jobs in each group and group sequence to minimize the
makespan. We show that jobs in each group are scheduled in nondecreasing order of its release time and
the groups are arranged in nondecreasing order of some certain conditions. We also present a polynomial
time solution procedure for the special case of the proposed problem.


---

## Body

## 1. Introduction

In traditional scheduling, job processing times are assumed to be fixed and known (Pinedo [1]). However, in reality, we often encounter settings in which the job processing times vary with learning effect (Cheng et al. [2] and Lee et al. [3]), deterioration effect (Alidaee and Womer [4], Cheng et al. [5], and Yin et al. [6]), time dependent effect (Gawiejnowicz [7], Zhang et al. [8], and Yin et al. [9]), and positional effect (Rustogi and Strusevich [10, 11], Bachman and Janiak [12], and Yin et al. [13]). Rustogi and Strusevich [14] combined all kinds of effect in a paper which considered the two classical objectives: the makespan and the sum of the completion times.In the second place, many manufactures have implemented the concept of group technology (GT. Burbidge [15]); it is conventional to schedule continuously all jobs from the same group. Group technology that groups similar products into families helps increase the efficiency of operations and decrease the requirement of facilities (Mitrofanov [16], Janiak and Kovalyov [17], and Webster and Baker [18]). In this paper, we do not assume that all maintenance periods are identical and allow each one of them to leave the processing conditions of the machine in a different state. We deal with a more general concept of a group setup time performed by the processing group. Thus, the effects that change the actual group setup time may become additionally dependent on the actual processing times of jobs before the proposed group.Rustogi and Strusevich [10] presented real-life examples: “These general positional effects can be found in practice as well. Extending the coursework marking example above, after marking a certain number of scripts, the teacher might get tired or bored, her attention becomes less focused and each new script may even take longer to mark than the one before. We are sure our academic colleagues know this feeling, and they also know the remedy: take a break, have a cup of coffee.” However, to the best of our knowledge, only few results concerning scheduling models and problems with position dependent processing times and group technology simultaneously are known. But combining the group technology with start time dependent processing times is more common. For the case that setup time of each group is a fixed constant, Wang et al. [19] considered single machine group scheduling in which the actual processing time of a job is a general linear decreasing function of its starting time; for the makespan minimization problem and total completion time minimization problem they showed that some problems can be solved in polynomial time. Xu et al. [20] considered the single machine scheduling problems with group technology and ready times; the job processing times are described by a function which is proportional to a linear function of time; the setup times of groups are assumed to be fixed and known; it showed that minimizing the makespan with ready times can be solved in polynomial time and proposed a heuristic algorithm. J.-B. Wang and J.-J. Wang [21] continued the work of Xu et al. [20]; they considered a more general deterioration model than the group setup times and job processing times; the objective is to minimize the makespan. They showed that the problem can be solved in polynomial time when start time dependent processing times and group technology are considered simultaneously.Motivated by the ideas of Rustogi and Strusevich [14] and J.-B. Wang and J.-J. Wang [21], we consider the single machine scheduling problem with ready times of the jobs under the group technology assumption and position dependent processing times. Our objective is to find the optimal group sequence and the optimal job sequence to minimize the makespan. The rest of the paper is organized as follows. In the next section we describe the formulation of our problem. In Section 3, we consider the solution method for minimizing makespan. In Section 4, a reduced model will be introduced and proposed a polynomial time algorithm. The conclusion is given in the last section.


## 2. Problem Description

The independent jobsJ1,J2,…,Jn have to be processed on a single machine. They are nonpreemptive and to be grouped into k groups: G[1],G[2],…,G[k]. The jobs in the same group are consecutively processed as long as the job has arrived; a setup time is required if the machine switches from one group to another and all setup times are positive. Assume that each group contains a total of ni jobs, so that the permutation of jobs in the ith group is given by π[i]={π[i](1),π[i](2),…,π[i](n[i])}, where ∑i=1k‍n[i]=n. Let rπ[i](r) represent the ready (arrival) time of the rth job in group Gi. Depending on the choice of groups and the order in which they are performed, the actual processing time of a job Jj(j=π[i](r)), scheduled in position r(1≤r≤ni) in group Gi(1≤i≤k), is given as follows:(1)pjir=pjgir,1≤i≤k,1≤r≤ni,where g[i](r) denotes positive group-dependent job-independent positional factors of the rth job in group Gi; we call the values g[i](r) deterioration factors.Furthermore, since the number of jobs,ni, in each group and the total duration of each group, Fi, are known, the actual setup time si is defined as follows:(2)si=aiFi-1,1≤i≤k,where ai (>0) is the deterioration rate of the group Gi. The deterioration factors g[i](r) are given in the form of a collection of ordered array of numbers:(3)1≤gi1≤gi2≤⋯≤gini,i=1,2,…,k,and rπ[i](r), pπ[i](r) satisfy the following relations: when rπ[i](1)≤rπ[i](2)≤⋯≤rπ[i](ni), there are(4)pπi1≥pπi2≥⋯≥pπini,i=1,2,…,k.For a given scheduleπ, let Cπ[i](r)=Cπ[i](r)(π) denote the completion time of job Jπ[i](r), and Cmax⁡=max⁡Cπir∣i=1,2,…,k;r=1,2,…,ni represent the makespan of a given schedule. Using the three-field notation schema in scheduling problems (Graham et al. [22]), the makespan minimization problem is denoted as 1∣rj, pj[i](r)=pjg[i](r), si=aiFi-1, GT∣Cmax⁡, where GT denote group technology.


## 3. The Solution Method

In the following section, we will give the solution method so that the single machine minimization scheduling problem with deteriorating jobs and ready times can be solved under certain conditions. Firstly, we consider that all jobs can be processed in one group; that is,k=1.Lemma 1.
For the problem1∣rj, pj(r)=pjg(r)∣Cmax⁡, where g(r) meets (3), the optimal job sequence can be obtained by sequencing the jobs in nondecreasing order of rj.Proof.
Suppose thatπ={S1,Ji,Jj,S2} and π′={S1,Jj,Ji,S2} are two job sequence, where S1 and S2 denote a partial sequence (note that S1 and S2 may be empty), and the difference between π and π′ is a pairwise interchange of two adjacent jobs Ji and Jj. In addition, the completion time of the last job of S1 in sequence π(π′) is denoted by A. Then, the completion times of job Ji and Jj under π are(5)Ciπ=max⁡⁡A,ri+pigr=max⁡⁡A+pigr,ri+pigr,(6)Cjπ=max⁡⁡Ciπ,rj+pjgr+1=max⁡⁡A+pigr+pjgr+1,ri+pigr+pjgr+1,rj+pjgr+1.Similarly, the completion times of jobs Jj and Ji under π′ are(7)Cjπ′=max⁡⁡A,rj+pjgr=max⁡⁡A+pjgr,rj+pjgr,(8)Ciπ′=max⁡⁡Cjπ′,ri+pigr+1=max⁡⁡A+pjgr+pigr+1,rj+pjgr+pigr+1,ri+pigr+1.
Suppose thatri≤rj, based on (6) and (8), we have(9)Ciπ′-Cjπ=max⁡⁡A+pjgr+pigr+1,rj+pjgr+pigr+1,ri+pigr+1-max⁡⁡A+pigr+pjgr+1,ri+pigr+pjgr+1,rj+pjgr+1.Based on the formula (3) pi≥pj, g(r)≤g(r+1), and the values of ri, rj, and A, we divide these values into three cases as follows.(1)
ri≤rj≤A; that is, jobs Ji and Jj have arrived at time A; then(10)Ciπ′-Cjπ=A+pjgr+pigr+1-A+pigr+pjgr+1=pi-pjgr+1-gr≥0.(2)
ri≤A<rj; that is, job Ji has arrived before time A, and Jj has not arrived at time A; then(11)Ciπ′-Cjπ=rj+pjgr+pigr+1-A+pigr+pjgr+1=rj-A+pi-pjgr+1-gr>0.(3)
A<ri≤rj; that is, jobs Ji and Jj have not arrived at time A; then(12)Ciπ′-Cjπ=rj+pjgr+pigr+1-ri+pigr+pjgr+1=rj-A+pi-pjgr+1-gr≥0.In conclusion, we have Ci(π′)≥Cj(π). Repeating this interchange argument, an optimal schedule can be obtained by sequencing the jobs in nondecreasing order of rj.Next, we consider the problem1∣rj, pj[i](r)=pjg[i](r), GT∣Cmax⁡; assume that B denotes the completion time of the (i-1)th group and rπ[i](1)≤rπ[i](2)≤⋯≤rπ[i](ni) is satisfied in group Gi. Then we have(13)Cπi1=max⁡⁡B+aiB,rπi1+pπi1gi1=max⁡⁡1+aiB+pπi1gi1,rπi1+pπi1gi1,Cπi2=max⁡⁡Cπi1,rπi2+pπi2gi2=max⁡⁡1+aiB+∑r=12pπirgir,rπi1+∑r=12pπirgir,rπi2+pπi2gi2,Cπi3=max⁡⁡Cπi2,rπi3+pπi3gi3=max⁡⁡1+aiB+∑r=13pπirgir,rπi1+∑r=13pπirgir,rπi2+∑r=23pπirgir,rπi3+pπi3gi3,⋮Cπini=max⁡⁡1+aiB+∑r=1nipπirgir,rπi1+∑r=1nipπirgir,rπi2+∑r=2nipπirgir,…,rπini+pπinigini=max⁡⁡1+aiB+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir,where(14)rπiBi+∑r=Binipπirgir=max⁡⁡rπi1+∑r=1nipπirgir,rπi2+∑r=2nipπirgir,…,rπini+pπinigini,Bi∈1,2,…,ni,i=1,2,…,k.Theorem 2.
For the problem1∣rj, pj[i](r)=pjg[i](r), si=aiFi-1, GT∣Cmax⁡, where g[i](r) satisfies formula (3), and pπ[i](r),rπ[i](r) satisfy formula (4). An optimal schedule can be obtained by the conditions as follows.
If (1) jobs in each group are scheduled in nondecreasing order ofrπ[i](j), that is,(15)rπi1≤rπi2≤⋯≤rπini,i=1,2,…,k,and if (2) the groups are arranged in nondecreasing order of(16)rπiBi-∑r=1Bi-1pπirgir1+ai,∑r=1nipπirgirai,where(17)rπiBi+∑r=Binipπirgir=max⁡⁡rπi1+∑r=1nipπirgir,rπi2+∑r=2nipπirgir…,rπini+pπinigini,where Bi∈1,2,…,ni, i=1,2,…,k.Proof.
In the same group, the result of (1) can be easily obtained by Lemma1. Next, we consider the case in item (2). Let π and π′ be a pairwise interchange of two adjacent groups Gi and Gj, that is, π=S1,Gi,Gj,S2 and π′=[S1,Gj,Gi,S2], where S1 and S2 are partial sequences. Further, we assume that B denotes the completion time of the last job in S1. To show π dominates π′, it suffices to show that Cπjnj(π)≤Cπini(π′). Under π, using (13), we obtain that the completion time of group Gi is(18)Cπiniπ=max⁡⁡1+aiB+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir,and the completion time of the group Gj is(19)Cπjnjπ=max⁡⁡1+ajCπjniπ+∑r=1njpπjrgjr,rπjBj+∑r=Bjnjpπjrgjr=max⁡⁡1+aj1+aiB+1+aj∑r=1nipπirgir+∑r=1njpπjrgjr,1+ajrπiBi+∑r=Binipπirgir+∑r=1njpπjrgjr,rπjBj+∑r=Bjnjpjrgjr=max⁡⁡max⁡⁡1+aj1+aiB,1+ajrπiBi-∑r=1Bi-1pπirgir+1+aj∑r=1nipπirgir+∑r=1njpπjrgjr,rπjBj+∑r=Bjnjpjrgjr.Under π′, the completion time of the group Gj is(20)Cπiniπ=max⁡⁡1+aiB+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir,and the completion time of the group Gi is(21)Cπiniπ′=max⁡⁡1+aiCjnjπ′+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir=max⁡⁡1+ai1+ajB+1+ai∑r=1njpπjrgjr+∑r=1nipπirgir,1+airπjBj+∑r=Bjnjpπjrgjr+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir=max⁡⁡max⁡⁡1+ai1+ajB,1+airπjBj-∑r=1Bj-1pπjrgjr+1+ai∑r=1njpπjrgjr+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir.Suppose that(22)rπiBi-∑r=1Bi-1pπirgir1+ai≤rjBj-∑r=1Bj-1pπjrgjr1+aj,∑r=1nipπirgirai≤∑r=1njpπjrgjraj;that is(23)1+ajrπiBi-∑r=1Bi-1pπirgir≤1+airπjBj-∑r=1Bj-1pπjrgjr,aj∑r=1nipπirgir≤ai∑r=1njpπjrgjr.Based on (19) and (21), we have(24)Ciniπ′-Cjnjπ=max⁡⁡max⁡⁡1+ai1+ajB,1+airπjBj-∑r=1Bj-1pπjrgjr+1+ai∑r=1njpjrgjr+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir-max⁡⁡max⁡⁡1+ai1+ajB,1+ajrπiBi-∑r=1Bi-1pπirgir+1+aj∑r=1nipπirgir+∑r=1njpπjrgjr,rπjBj+∑r=Bjnjpπjrgjr≥max⁡⁡max⁡⁡1+ai1+ajB,1+ajrπiBi-∑r=1Bi-1pπirgir+1+aj∑r=1nipπirgir+∑r=1njpπjrgjr,rπiBi+∑r=Binipπirgir-max⁡⁡max⁡⁡1+ai1+ajB,1+ajrπiBi-∑r=1Bi-1pπirgir+1+aj∑r=1nipπirgir+∑r=1njpπjrgjr,rπjBj+∑r=Bjnjpπjrgjr=0.Therefore Cπini(π′)≥Cπ[j](nj)(π); this completes the proof.


## 4. A Reduced Model

In this section, we explore a single machine model, which can be expressed as a special case of the general problem1∣rj, pj[i](r)=pjg[i](r), si=aiFi-1, GT∣Cmax⁡; that is, the actual setup time si of group Gi is a constant t (>0). The main purpose of this section is to give a streamlined conclusion and algorithm. Assume that B denotes the completion time of the (i-1)th group and rπ[i](1)≤rπ[i](2)≤⋯≤rπ[i](ni) is satisfied in the group Gi. Then we have(25)Cπini=max⁡⁡B+t+∑r=1nipπirgir,rπi1+∑r=1nipπirgir,rπi2+∑r=2nipπirgir,…,rπini+pπinigini=max⁡⁡B+t+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir,where(26)rπiBi+∑r=Binipπirgir=max⁡⁡rπi1+∑r=1nipπirgir,rπi2+∑r=2nipπirgir,…,rπini+pπinigini,and B(i)∈{1,2,…,ni}, i=1,2,…,k. Then Cπ[i](ni) can be written as(27)Cπini=max⁡⁡B+t,rπiBi-∑r=1Bi-1pπirgir+∑r=1nipπirgir.Theorem 3.
For the problem1∣rj, pj[i](r)=pjg[i](r), si=t, GT∣Cmax⁡ the g[i](r) satisfies formula (3), and pπ[i](r),rπ[i](r) satisfy formula (4); the optimal schedule satisfies the following.(1)
Jobs in each group are scheduled in nondecreasing order ofrj; that is,(28)rπi1≤rπi2≤⋯≤rπini,i=1,2,…,k.(2)
The groups are arranged in nondecreasing order ofriB(i)-∑r=1B(i)-1‍pπ[i](r)g[i](r), where(29)rπiBi+∑r=Binipπirgir=max⁡⁡rπi1+∑r=1nipπirgir,rπi2+∑r=2nipπirgir,…,rπini+pπinigini,where Bi∈1,2,…,ni, i=1,2,…,k.Proof.
Similar to Theorem2, using the two exchange methods, under π, based on (27), we can obtain the completion time of Gi(30)Cπiniπ=max⁡⁡B+t,rπiBi-∑r=1Bi-1pπirgir+∑r=1nipπirgir,and the completion time of Gj(31)Cπinjπ=max⁡⁡Cπiniπ+t,rπjBj-∑r=1Bj-1pπjrgjr+∑r=1njpπjrgjr=max⁡⁡B+2t+∑r=1nipπirgir+∑r=1njpπjrgjr,rπiBi+t+∑r=Binipπirgir+∑r=1njpπjrgjr,rπjBj+∑r=Bjnjpπjrgjr.Under π′, the completion times of Gj and Gi are(32)Cπjnjπ′=max⁡⁡B+t,rπjBj-∑r=1Bj-1pπjrgjr+∑r=1njpπjrgjr,Cπiniπ′=max⁡⁡Cπjnjπ′+t,rπiBi-∑r=1Bi-1pπirgir+∑r=1nipπirgir=max⁡⁡B+2t+∑r=1njpπjrgjr+∑r=1nipπirgir,rπjBj+t+∑r=Bjnjpπjrgjr+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir.Supposing that rπ[i](B(i))-∑r=1B(i)-1‍pπ[i](r)g[i](r)≤rπ[j](B(j))-∑r=1B(j)-1‍pπ[j](r)g[j](r), based on (31) and (32), we have(33)Cπiniπ′-Cπjnjπ=max⁡⁡B+2t+∑r=1njpπjrgjr+∑r=1nipπirgir,rjBj+t+∑r=Bjnjpπjrgjr+∑r=1nipπirgir,rπiBi+∑r=Binipπirgir-max⁡⁡B+2t+∑r=1nipπirgir+∑r=1njpπjrgjr,rπiBi+t+∑r=Binipirgir+∑r=1njpπjrgjr,rπjBj+∑r=Bjnjpπjrgjr=rπjBj+t+∑r=Bjnjpπjrgjr+∑r=1nipπirgir-rπiBi+t+∑r=Binipπirgir+∑r=1njpπjrgjr=rπjBj-∑r=1Bj-1pjrgjr-rπiBi-∑r=1Bi-1pπirgir≥0.Therefore Cπ[i](ni)(π′)≥Cπ[j](nj)(π); this completes the proof.For the problem1∣rj, pj[i](r)=pjg[i](r), si=t, GT∣Cmax⁡, we provide an algorithm based on the result of Theorem 3 as follows.Algorithm 4.
Step 1. Jobs in each group are scheduled in nondecreasing order of rir; that is, (34)rπi1≤rπi2≤⋯≤rπini,i=1,2,…,k.Step 2. Let(35)rπiBi+∑r=Binipπirgir=max⁡⁡rπi1+∑r=1nipπirgir,rπi2+∑r=2nipπirgir,…,rπini+pπinigini,where Bi∈1,2,…,ni, i=1,2,…,k.
CalculateB(i) and rπ[i](B(i))-∑r=1Bi-1‍pπirgir, i=1,2,…,k.
Step 3. Groups are scheduled in nondecreasing order of ρ(Gi)=rπ[i](B(i))-∑r=1B(i)-1‍pπ[i](r)g[i](r).
Obviously, the complexity of obtaining the optimal job sequence within a certain groupGi is O(nilog⁡ni) and that of obtaining the optimal group sequence is O(klog⁡k). It is easy to show that ∑i=1k‍O(nilog⁡ni)≤O(nlog⁡n). Hence, the complexity of Algorithm 4 is at most O(nlog⁡n). In addition, we demonstrate Algorithm 4 by the following example.Example 5.
There are eight jobs(n=8) divided into three groups (k=3) to be processed on a single machine.
Letsi=3, and G1={Jπ[1](1),Jπ[1](2)}, pπ[1](1)=10, pπ[1](2)=8, g[1](1)=1, g[1](2)=1.2, rπ[1](1)=3,rπ[1](2)=7; G2={Jπ[2](1),Jπ[2](2),Jπ[2](3)}, pπ[2](1)=9, pπ[2](2)=10, pπ[2](3)=7, g[2](1)=1.1, g[2](2)=1.3, g[2](3)=1.5, rπ[2](1)=9, rπ[2](2)=2, rπ[2](3)=12; G3={Jπ[3](1),Jπ[3](2),Jπ[3](3)}, pπ[3](1)=8, pπ[3](2)=5, pπ[3](3)=10, g[3](1)=1, g[3](2)=1.3, g[3](3)=1.3, g[3](3)=1.4, rπ[3](1)=14, rπ[3](2)=15, rπ[3](3)=3.Solution. According to Algorithm 4, we solve Example 5 as follows.Step 1. The optimal job sequence in G1, G2, G3 is(36)G1:Jπ11⟶Jπ12;G2:Jπ22⟶Jπ21⟶Jπ23;G3:Jπ33⟶Jπ31⟶Jπ32.Step 2. Calculating B(i) and ρ(Gi), we compute the following values for each group:(37)G1:rπ1B1+∑r=B12pπ1rg1r=max⁡⁡rπ11+∑r=12pπ1rg1r,rπ12+pπ12g12=max⁡⁡3+19.6,7+9.6=22.6;B(1)=1, that is, the jobs from the first to continuous processing in group G1, ρ(G1)=rπ[1]((1)=3:(38)G2:rπ2B2+∑r=B23pπ2rg2r=max⁡⁡rπ21+∑r=13pπ2rg2r,rπ22+∑r=23pπ2rg2r,rπ23+pπ23g23=max⁡⁡2+33.2,9+22.2,12+10.5=35.2;B(2)=1, that is, the jobs from the first to continuous processing in group G2, ρ(G2)=rπ[2](1)=2:(39)G3:rπ3B3+∑r=B33pπ3rg3r=max⁡⁡rπ31+∑r=13pπ3rg3r,rπ32+∑r=23pπ3rg3r,rπ33+pπ33g33=max⁡⁡3+27.4,14+17.4,15+7=31.4;B(3)=2, that is, the jobs from the second to continuous processing in group G3, ρ(G2)=rπ[3](2)-pπ[3](1)g[3](1)=4.Step 3. Since ρ(G2)<ρ(G1)<ρ(G3), hence, the optimal group sequence is G2→G1→G3.Therefore, the optimal schedule is[Jπ[2](2)→Jπ[2](1)→Jπ[2](3)]→[Jπ[1](1)→Jπ[1](2)]→[Jπ[3](3)→Jπ[3](1)→Jπ[3](2)], and the optimal value of the makespan is 90.2.


## 5. Conclusion

In this paper we have considered the scheduling problem with group technology and position dependent processing times, for the case that group setup times are linearly related to the completion time of the former group and the job processing times are the general nondecreasing function of the positional factors. We showed that the makespan minimization problem with ready times can be solved under certain conditions. A reduced model can be considered as special case of our general model. Furhermore, we present anO(nlog⁡n) time algorithm to solve the proposed problem.



---

*Source: 206230-2015-07-28.xml*