FJS Problem Under Machine Breakdowns

Abstract

One of the most challenging problems in manufacturing field is to solve the flexible job shop (FJS) problem subject to machines breakdown. In this paper, we propose two rescheduling solutions to handle machine breakdowns: a PSO-based solution and a shifting-based solution. The first solution aims to improve the robustness while the second solution aims to improve the stability.

1 Introduction

The FJS Problem consists in scheduling a set of operations forming jobs on a limited set of machines such that the maximal completion time of all operations is minimized. FJS problem is a strongly NP-hard problem and handling random machine breakdowns further complicates the problem. In the context of machines breakdown, there are two phases: a prescheduling phase (before the breakdown) and a rescheduling phase (after the breakdown). The quality of a rescheduling solution is often measured by three criteria: completion time of all jobs, robustness and stability comparing to the prescheduling solution [2]. Machines breakdown can be handled at priori (preventive) [1], at posteriori (curative) [5,6,7] or at both stages [3]. In [1] a genetic algorithm with idle-time insertions is proposed. In [5, 6], a genetic algorithm combining right shift strategy (RSS) and route is proposed as a curative solution. In [3] authors use the particle swarm optimization (PSO) and RSS to handle machine breakdowns.

In this paper, two curative solutions are presented: PSO historic route changing (PSO-HRC) and modified shifting strategy (MSS). The first aims to improve the robustness while the second aims to improve the stability. Two assumptions are used: a single machine breakdown and non-resumable mode (i.e. affected operations have to be restarted).

This paper is organized as follows. Sections 2 and 3 define respectively the FJS problem under breakdown machine, and the PSO meta-heuristic. Sections 4 and 5 present respectively the proposed curative solutions and the experimental results. Section 6 concludes the paper.

2 The FJS Problem with Stability and Robustness Criteria

The FJS problem is defined by:

$J = \left\{ {J_{1} ,J_{2} \ldots J_{n} } \right\}$ a set of n independent jobs, $M = \left\{ {m_{1} ,m_{2} \ldots m_{k} } \right\}$ a set of machines and $O = \left\{ {\left( {O_{11} ,O_{12} , \ldots } \right),\left( {O_{21} ,O_{22} , \ldots } \right) \ldots \left( {O_{n1} ,O_{n2} , \ldots } \right)} \right\}$ the set of operations, where $O_{ji }$ is operation i of job j.

The goal is to find a schedule of operations that minimizes the completion times of all jobs (MakeSpan of the schedule), where, $C_{j}$ is the completion time of job J:

$$ MS = Minimize\left[ {Max\left( {C_{1} ,C_{2} , \ldots .C_{j} } \right)} \right] $$

(1)

We will use the same definitions of robustness and stability of the rescheduling solution as in [1, 8]. Two formulas are used to measure robustness:

$$ RM1 = \frac{{MS_{r} - MS_{p} }}{{MS_{p} }} \times 100\% $$

(2)

where, $MS_{p}$ is the makespan of the prescheduling solution and $MS_{r }$ is the makespan of the rescheduling solution. A schedule is robust if RM1 is low.

$$ RM2 = \sum\nolimits_{{{\text{i}} = 1}}^{O} {\frac{{Load_{m} }}{{Load_{tot} }}Pt_{i} } $$

(3)

$$ Load_{tot} = \sum\nolimits_{{{\text{m}} = {\text{i}}}}^{\text{k}} {Load_{m} } $$

(4)

where, $Pt_{i }$ is the processing time of the i and $Load_{m}$ is the workload of the Machine handling operation i. A schedule is robust if RM2 is high.

Three formulas are used to measure stability:

$$ SM1 = \sum\nolimits_{j = 1}^{n} {\sum\nolimits_{i = 1}^{qj} {\left| {c_{{O_{jip} }} - c_{{O_{jir} }} } \right|} } $$

(5)

$$ SM2 = \frac{{\sum\nolimits_{{{\text{j}} = 1}}^{n} {\sum\nolimits_{i = 1}^{qj} {\left| {C_{{O_{jir} }} - C_{{O_{jir} }} } \right|} } }}{{\sum\nolimits_{{{\text{j}} = 1}}^{n} {Oj} }} $$

(6)

$$ SM3 = \frac{{\sum\nolimits_{{{\text{j}} = 1}}^{n} {\sum\nolimits_{i = 1}^{qj} {\left| {C_{{O_{jio} }} - C_{{O_{jir} }} } \right|} } }}{{\sum\nolimits_{i = 1}^{n} {\sum\nolimits_{j = 1}^{qi} {AO_{j} } } }} $$

(7)

where, n is the number of jobs, ${\text{q}}_{\text{j}}$ is the number of operations in job j, ${\text{c}}_{{{\text{O}}_{\text{ijP}} }}$ the completion time of ${\text{O}}_{\text{ji}}$ in the pre-schedule, ${\text{c}}_{{{\text{O}}_{\text{ijr}} }}$ the completion time of ${\text{O}}_{\text{ji}}$ in the re-schedule, and ${\text{O}}_{\text{j}}$ the total number of operations of job j and, ${\text{AO}}_{\text{i}}$ the total number of operations in jobs j affected by the breakdown.

3 The PSO Meta-heuristic

The PSO [3] works by having a population of candidate solutions that are moving around in the search space in order to improve their current solutions. The movements of particles are guided by their own best-known position in the search-space as well as the entire swarm’s best-known position. At each instant, each particle p takes a new position vector noted $X_{p} \left( t \right)$, and new velocity vector noted $V_{p} \left( t \right)$, are computed using:

$$ V_{p,d} \left( {t + 1} \right) = w.V_{p,d} \left( t \right) + K_{1} .r _{1} \left( {Xbest_{p,d} \left( t \right) - X_{p,d} \left( t \right)} \right) + K_{2} .r_{2} \left( {Xgbest_{p,d} \left( t \right) - X_{p,d} \left( t \right)} \right) $$

(8)

$$ X_{p,d} \left( {t + 1} \right) = X_{p,d} \left( t \right) + V_{p,d} \left( {t + 1} \right) $$

(9)

Where, d is the dimension of vectors, $Xbest_{p} \left( {t - 1 } \right)$ is the best position reached by the particle up to time $t - 1,Xgbest_{p} \left( t \right)$ is the best position ever found by the whole swarm. $r_{1}$ and $r_{2}$ are random numbers in the interval [0, 1], $K_{1}$ and $K_{2}$ are positive constant called respectively the coefficient of the self-recognition component, and the coefficient of the social component. w a dynamic inertia coefficient varying over time [7].

4 The Proposed Rescheduling Solutions

This section presents the two rescheduling approaches (MSS and PSO-HRC). We use the PSO metaheuristic to determine the prescheduling solution that minimizes the total workload and the makespan.

Let $X_{pt}$ be the set of operations that are already triggered before the breakdown and $X_{pr}$ the set of operations not triggered yet. The MSS approach starts by determining: the operation $AO_{jim}$ directly affected by the breakdown, the indirectly affected operations $O_{{j\left( {i + 1} \right)m^{{\prime }} }}$ of the same job, and the indirectly affected operations $O_{{j^{{\prime }} {\text{i}}^{{\prime }} {\text{m}}}}$ mapped to machine m. Then the MSS performs a guided right shift according to Algorithm_1.

In the PSO-HRC approach, a leader historic table is maintained during the prescheduling phase. This table contains the best scheduling solutions reached by leading particles. Once a machine is broken down, the position vector $X_{p}$ is divided into two parts $X_{pt}$ and $X_{pr}$, then a search of $X_{pt}$ in the historic_table is performed followed by an update of $X_{{p{\text{r}}}}$. Algorithm_2 presents the main steps of PSO-HRC.

5 Experimental Results

In this section we present the simulation results of the proposed rescheduling algorithms then we compare them to those obtained by the idle time insertion (ITI) [1] and the random route changing (RRC). The comparison criteria are robustness RM1 (Eq. 2) and RM2 (Eq. 3), stability SM1, SM2 and SM3 (Eqs. 5, 6 and 7), the makespan MS (Eq. 1) and the total workload (Eq. 4). Due to lack of space we present the experimental results only for two FJS problem instances: an instance of 10 machines and 10 jobs with a total flexibility, and an instance of 8 machines and 8 jobs with a partial flexibility. The probability of machine breakdowns, the machine repair period, the occurrence time of the breakdown and the four disruption scenarios are chosen in a similar manner as in [1]. These scenarios are listed in Table 1. Figure 1 shows the prescheduling solutions (i.e. before breakdown) obtained by the PSO algorithm after 20 trials using 500 particles and 500 iterations.

Table 1. Breakdown scenarios

Fig. 1.

Prescheduling schedules of the FJS instances

Tables 2, 3 and 5 compare the fitness, the workload and the robustness of the four scheduling algorithms. We notice the out performance of PSO-HRC. RRC and ITI give best result if there is only one affected operation with a short repair time (as in SN2 and SN4). Tables 4 and 6 compares the stability of the four rescheduling algorithms. We notice that MSS gives the best stability but not the best fitness.

Table 2. Problem 8*8, SN_1 & SN_2: fitness, robustness, workload and slack time

Table 3. Problem 8*8, SN_3 & SN_4: fitness, robustness, workload and slack time

Table 4. Problem 8*8: stability

Table 5. Problem 10*10, SN_1 & SN_2: fitness, robustness, workload and slack time

Table 6. Problem 10*10: stability

6 Conclusions

In this paper, we proposed two rescheduling solutions (PSO-HRC and MSS) to solve the FJS problem under machine breakdowns. Comparing to other solutions, the PSO-HRC provides better makespan, better workload and better robustness. While the MSS offers a better stability. In our future work we will target other types of machine breakdowns such as the partial breakdowns and the breakdowns causing changes on the durations of operations.