Robust Job Shop Scheduling Problem: Mathematical Models, Exact and Heuristic Algorithms

Accepted Manuscript

Robust Job Shop Scheduling Problem: Mathematical Models, Exact and Heuristic Algorithms

Amin Jamili
PII: / S0957-4174(16)30018-5
DOI: / 10.1016/j.eswa.2016.01.054
Reference: / ESWA 10512
To appear in: / Expert Systems With Applications
Received date: / 1 January 2015
Revised date: / 18 January 2016
Accepted date: / 26 January 2016
Please cite / this / article / as: Amin Jamili , Robust Job / Shop Scheduling Problem: Mathemat-
ical Models, / Exact and / Heuristic Algorithms, Expert / Systems With Applications (2016), doi:

10.1016/j.eswa.2016.01.054

This is a PDF Þle of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its Þnal form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.

ACCEPTED MANUSCRIPT

Highlights

In real world applications, the job shop schedules are contaminated with disruptions.

Robust schedules should be able to absorb the predefined range of disruptions.

We propose 2 robustness measures.

We propose 2 exact and 2 heuristic methods to reach a robust solution.

1

ACCEPTED MANUSCRIPT

Robust Job Shop Scheduling Problem: Mathematical Models, Exact and Heuristic Algorithms

Amin Jamili1

School of Industrial Eng., College of Engineering, University of Tehran, Tehran, Iran,

Tel.: +98-21-23154144, Fax.: +98-21-81982428

Abstract

Job shop scheduling problem is very important one in real application of many kind of industries. In the real world applications, there exists many different kinds of disruptions with different sizes. In this situation, beyond the optimality of the final solution, its ability to absorb disruptions is vital, so that the final solution remains feasible in the case of occurring predicted disruptions. In this paper a robust job shop scheduling problem under disruptions is considered. It is intended to generate robust schedules which are able to absorb a predefined range of disruptions. For this reason, two robustness indices are proposed and the related formulas for computing the required buffer times to reach the desired robustness level are proposed. For this purpose, four methods are proposed to solve the variant defined robust job shop scheduling problem, including (1) a mathematical model, (2) a branch and bound algorithm, (3) a beam search algorithm, and (4) a meta-heuristic algorithm based on the particle swarm optimization (PSO) method. The first and second methods result in optimum solution. As the size of the problem increases, the required time to find the optimum solutions raises, so that no solutions can be achieved in rational amount of time, e.g. one hour. Therefore, the third and fourth methods are proposed to find good solutions even for large-scale problem in a limited amount of time. Finally, the algorithms are compared using some randomly generated instances. The results show that each algorithm can outperform the others in different conditions.

Key words: Job Shop Scheduling; Robustness Index; Disruption; Branch and Bound; ParticleSwarm Optimization.

1. Introduction

A job shop-scheduling problem (JSSP) is associated with the manufacturing industry with many practical applications on the scheduling operations in a shop environment. JSSP has been investigated to a varied depth in the literature. The present paper intends to address JSSP under disruptions and illustrates some novel methods to achieve robust schedules.

Recently, the idea of robust optimization has gained a lot of interest amongst many researchers. In classical optimization problems, all input parameters are exactly supposed to be known. However, this is a fact that the parameters are almost always contaminated with disruptions. In scheduling problems, the processing times as well as release dates are common parameters which are under noises during real world applications.

The two main categories reported on scheduling under uncertainties are those that, model uncertainty by probability density functions and those that immune the schedules against possible disruptions that may arise without considering any specific probability distribution, known as the robustness approach. Pinedo (2002) has presented a concise summary of

1Corresponding author

2

ACCEPTED MANUSCRIPT

stochastic scheduling results. The optimization method for the problem of J2 || Cmax has been presented in this study. Singer (2000) has modeled a job shop scheduling problem with random processing times, where the expected total weighted tardiness must be minimized. The processing times are supposed to be in discrete distributions similar to normal, exponential and uniform ones. The author has ultimately selected an active scheduling generation as the branching scheme. Tavakkoli-Moghaddam, et al., (2005) have proposed a hybrid method containing neural networks and simulated annealing to solve a non-linear stochastic JSSP. Artigues, et al. (2005) have also discussed the flexibility of solutions as a means to achieve robust shop scheduling. Their proposed approach is relied on computing several off-line schedules so that in practice the decision makers can switch from one solution to another while the disruptions occur. The authors believe that, this method serves more flexibility and therefore more robustness in the schedule generation phase. Byeon , et al., (1998) have proposed the use of graph decomposition heuristic technique to improve the scheduling robustness. Their proposed method is relied on decomposition of JSSP into a set of sub-problems through solving a new generalized assignment problem. Recently Shafia, et al., (2010) have used the robust optimization approach proposed by Bertsimas & Sim (2004) to the JSSP. By this method a new mathematical model is generated which is robust against disruptions, where the robustness level is under control. Khatami, et al., (2015) addressed the β-robust job shop scheduling problem when the processing time of each operation is a normal random variable, and used the PERT approach to calculate the mean and variance of the longest path of the graph. This approach assumes the stochastic independence of the nodes, which is not a real one, and may results in inadequate solutions. Akker, et al., (2013) addressed finding robust solutions for job shop scheduling problem based on combination of local search and simulation, where because of the flexibility of simulation, each stochastic variable can have its own probability distribution, and the variables do not have to be independent. Pourseyed Aghaee, et al., (2011) proposed a robust mathematical model based on the Bertsimas and Sim approach and no solving approaches are proposed. Al-Hinai, and ElMekkawy, (2011) proposed a genetic algorithm for the problem of flexible job shop scheduling problem. In this paper, no buffer times are used, and the aim is to obtain a schedule that sequence the operations on machines in such a way that less impact on the overall performance of the schedule in case of disruptions happen.

In this paper a novel approach which is directly addressing the use of inserting buffer times into the schedule is proposed. For this reason the author of the present paper introduces two new robustness indices which are used to generate robust schedules as such that the desired robustness level to be under control. The first method is relied on the mathematical expectation of disruptions, while the second approach addresses the probability distribution function of disruptions. The required buffer times are generated in such a way that, they have the minimum effects on the optimization function value in one hand, and provide the desired level of robustness defined by the decision makers on the other hand.

The current paper is organized as follows: The author first presents the necessary notations and two new robustness indices in section 2. In section 3 a robust mathematical formulation is presented. Section 4 is death with explanation of the Branch and Bound (B&B) along with a heuristic beam search algorithm as well as PSO meta-heuristic algorithm. In section 5 the validity of algorithm as well as its effectiveness is demonstrated. Finally, the conclusion remarks are given at the end to summarize the contribution of this paper.

3

ACCEPTED MANUSCRIPT

2. Definition of robustness indices

In real world applications, where there exists the possibility of interruption occurrences, further to the optimality of schedules, the robustness of the schedules is highly important. The main purpose of generating robust schedules is to absorb interruptions which are likely to happen in practice. Generally the robustness of schedules in scheduling problems is achieved by embedding some buffer times amongst the operations. It is totally known that generating robust schedules is accompanied with worsening the objective function. As a result generating robust schedules which have minimum effects on the objective functions is highly invaluable. In the other words the author aims to insert some buffer times in the schedules which on the one hand have minimum effects on the objective function, but on the other hand results the desired robustness level.

In the present paper, the author proposes two robustness indices as such that prevents unnecessary buffer time assignments. In the first proposed method only the expected values of disruptions are to be known, while in the next, the distribution functions of disruptions are required.

In the remaining part of this section, beyond presenting the definition of delay propagation through the jobs and machines, the robustness indices as well as the proposed method to find the required buffer times are also investigated. Following notations are used to define the proposed robustness indices:

ij / Random variable of disruption occurrence of operation (i,j) disregarding the potential
remained disruptions effects of previously scheduled operations.
Dij / Random variable which denotes the delay of operation (i,j)
EDij /  / Expected value of Dij
tij / Processing time of operation ( i,j )
xij / Completion time of operation (i,j )
x´ij / Starting time of operation (i,j ), i.e. xij- tij
bijv / The required vertical buffer time before operation (i,j)
bijh / The required horizontal buffer time before operation (i,j)
ebijv / The existing vertical buffer time before operation (i,j)
ebijh / The existing horizontal buffer time before operation (i,j)
Bi / Set of machines met by job i

ASet of jobs

Remark 1: Each operation, e.g. (i,j), is not only affected by the possible disruptions whichmay occur during the operation (i,j), i.e. ij , but also is affected by the delays originated by the

other already scheduled operations. In other words, once a delay on an operation is occurred, its effects may impact the followed scheduled operations, as well. This phenomenon is called as delay propagation.

A simple example consists of 2 jobs and 2 machines, which is illustrated in Fig. 1. It shows how a schedule is affected by disruptions in case 2.

{Please insert Fig. 1 here}

4

ACCEPTED MANUSCRIPT

Fig. 1, case 1 illustrates a classical, i.e. non-robust, schedule. The non-zero existing buffer times are shown in case 1. An existing vertical buffer time, e.g. ebijv , is defined as the buffer time between operation (i,j) with operation(i,j´), while an existing horizontal buffer time, e.g. ebijh, is defined as the buffer time between operation (i,j) with operation(i´,j). Worth nothing

that in this paper, j´ is the machine which is met before machine j by job i. i´ is the job which precedes job i on machine j. Case 2 illustrates an actual schedule where possible disruptions have been occurred. Case 3 presents a robust schedule which is generated by inserting some

buffer times. As it is specified earlier, bijv and bijh are the required buffer times to individually

absorb the effects of vertical and horizontal non-absorbed delays on operation (i,j). Moreover, we have:

ebh /  x /  x
ij1 / ij1 / kj1
ebv /  x /  x
ij1 / ij1 / ij
ebh /  x /  x
kj / kj / ij
ebv /  x /  x
kj / kj / kj1

Considering case 2, the delays of operations are computed as follows:

Dij / ij
Dkj1 kj1 / xkj xkj1 / ,Dij xkj xij,0kj Dkj1 kj / kj1
Dkj / kj  maxDkj1
Dij1 ij1maxDij /  / 
xij1xij / ,Dkj1xij1xkj1,0ij1Dkj1 ij1kj1
 / 
and generally, one can find that:
Dij / ij  maxDij / xij xij,Dij xij xij,0, iA,jBi / (1)

Where, j´ is the machine which is met before machine j by job i. i´ is the job which is processed on machine j just before job i . Eq. 1 specifies the delay of operation (i,j). In this

 /  xij / specifies the effect of remained, i.e. non absorbed,
equation, the statement Dijxij
 /  xijindicates the amount of non-absorbed delay of
delay of operation (i,j´), while Dij xij

operation (i´,j) to the operation (i,j). In the current paper, these statements are called vertical and horizontal remained delays, respectively. By the proposed Eq. 1, we have computed the chain effects of all non-absorbed delays of all operations to other ones.

First robustness index

The author aims to generate such schedules which are robust against disruptions, where the amount of robustness is under control. To that end, two new robustness indices are proposed. The first one is only based on the expected values of disruptions. In order to measure the robustness level of schedules, index 2 is proposed.

EDijij, iA,jBi / (2)

Where, ij indicates the maximum allowable expected delay of operation (i,j). In other words

the author intends to find such schedules that in which the expected delay of operation (i,j) is less than a pre-determined threshold, i.e. ij . It is clear that as the amount of the specified

threshold, ij increases, the generated schedules are more robust while the amount of objective function deteriorates.

5

ACCEPTED MANUSCRIPT

Generating required buffer times

In order to generate the required buffer times, the effect of vertical and horizontal delays are investigated individually. Therefore, let bijv and bijh be the required buffer times to individually absorb the effect of vertical and horizontal non-absorbed delays on operation (i,j), respectively.

As previously in this paper was specified, the expected vertical delay of operation (i,j), equals:

E ED x x . It is aimed to find the required buffer timesbv such that index 2 is

ijijijijij

fulfilled. First note that bv x /  x / . Therefore, we have:
ij / ij / ij
Eij EDij bijvij, or / bijv  Eij EDijij, considering the fact that / bijv 0, it is
concluded that / bvcould be computed based on the following equation.
ij
bijv  / if (i,j) is not the first operation / (3)
corresponding with job i
0, / Otherwise

Similarly, the horizontal buffer time could be computed based on the following equation.

if (i,j) is not the first operation
bijh /  / scheduled on machine j / (4)
0, / Otherwise
Finally, in order to achieve a robust schedule, the starting time of operation (i,j) must be
computed so that constraint 5 is satisfied. / (5)
xij / maxxijbij / , xij /  bij / 
 / v / h

By the above explanation, disregarding the used solving methods like mathematical modeling, branch and bound algorithm, heuristic algorithms, etc., in order to obtain robust schedules which fulfill index 2, it is only necessary to satisfy constraint 5.

Second robustness index

As earlier was specified, the first proposed robustness index only utilizes the mathematical expectation of disruptions. However, in this section it is aimed at defining a robustness index where the distribution functions of disruptions are known. The second proposed robustness index is as follows:

PDij ,iA,jBi(6)

where,  and  , are called adjusting parameters and0 and 0, 1. In other words, it is

intended to generate robust schedules in which the probability of occurring a delay bigger than

is always smaller than  .

Generating required buffer times

6

ACCEPTED MANUSCRIPT

Before explaining the proposed method to compute the required buffer times corresponding to the robustness index 6, let extend the first example as shown in Fig. 2.

{Please insert Fig. 2 here}

The delay of operation (i,j-1) equals the following equation. / (7)
Dij1 / ij1 /  maxDij1 / xij1xij / ,Dlj1 / xij1xlj1 / ,0
 / 

{Please insert Fig. 3 here}

As it is shown in Fig. 3, in order to compute Dij1 , the delays associated with operations (i,(j-

1)´) and (i´,j-1), i.e.Dij1 / and Dlj1 , must be known first.
Consider Fig. 1- Case 3, where / Dij1 ij1maxDij / v / h / , and suppose
 ebij1,Dkj1 ebij1,0
that Dij /  ebijv1Dkj1 ebijh1and / Dkj1 ebijh10, then we have:
D /  / ij1 /  D /  ebh /  / ij1 /  / kj / 1 /  ebh / .
ij1 / kj1 / ij1 / ij1
It is also known that Dlj1 lj1 . Therefore we have:
h /  /  xij,lj1 /  / ,0.
Dij1ij1maxij1kj1ebij1 / xij1 / xij1xlj1
Now suppose that one intends to find the starting time of operation (i,j-1), i.e. x / , such that
ij1
PDij1 . It is easy to show that, to achieve such a robustness level, bijv1, and bijh1must
be found such that constraints 8, 9 and 10 are satisfied, respectively.
Pij1ij1kj1 ebijh1 bijv1 / (8)
Pij1lj1 bijh1 / (9)
Pij1  / (10)
Notice that constraint 10 must be always fulfilled, otherwise it is concluded that no robust
solutions which could satisfy index 6 exists.
Inequality 8 can be rewritten as follows:
Pij1ij1kj1 ebijh1 bijv1 /  , or Pij1ij1kj1ebijh1bijv1 /  1 
and finally:
 / f ij1 f ij1 / 
 /  /  /  1 , / (11)
 / fkj1dij1dij1dkj1
ij 1 / ij1kj1ebijh1bijv1 / 
A similar inequality can be obtained for inequality 9.

Now let define Sij as a set of operations which potentially cause the main delay for operation

(i,j). / For example, as earlier specified D /  / ij1 /  / kj1 /  ebh / , and / therefore / we / have
ij1 / ij1
S / i, j 1,k , j 1.Moreover,if / one / suppose / that / bv /  bh / , / then
ij1 / ij1 / ij1

Sij1i, j 1,i, j 1,k , j 1. By this assumption the critical path for computing therequired buffer time for operation (i, j) is the one highlighted in Fig 3-b.

In general case, in order to find a robust schedule which fulfills index 6, bijv , and bijh are to be found where constraints 12 and 13 are satisfied respectively.

7

ACCEPTED MANUSCRIPT

 / Sij / 1

 /  /  / 
......
 / v k,lSij
h / v
 /  kl  ebkl / bij
 / k ,l Sij / k ,l Sij
 / Sij / 1

 /  /  / 
......
 / h k,lSij
h / v
 /  kl  ebkl / bij
 / k ,l Sij / k ,l Sij


f kldkl1
k ,l Sij / 



f kl /  / dkl / 
 /  1 
k ,l Sij / 



(12)

(13)

Where, ebijh/v is the existing horizontal/vertical buffer time before operation (i,j), and is related to the critical path. Now suppose that bvbh , then we have SSi,j.

ijijiji j

Exponential distributions for processing times are studied by D. Lei (2011). Following proposition describes the assumption of equal distributions for disruptions.

Proposition1:Bytheassumptionofconsideringequalexponentialdistributionsfor

1

disruptions with rate parameter 1 , i.e. fij1eij , substituted for inequality 14.