Discrete Optimization
Solving the flexible job shop scheduling problem with sequence-dependent setup times

https://doi.org/10.1016/j.ejor.2017.08.021Get rights and content

Highlights

  • This study addresses flexible job shop scheduling problems.

  • Sequence dependent setup times are considered.

  • Structural properties are presented and well utilized.

  • The proposed algorithm generates competitive results.

Abstract

This paper addresses the flexible job shop scheduling problem with sequence-dependent setup times and where the objective is to minimize the makespan. We first present a mathematical model which can solve small instances to optimality, and also serves as a problem representation. After studying structural properties of the problem using a disjunctive graph model, we develop a tabu search algorithm with specific neighborhood functions and a diversification structure. Extensive experiments are conducted on benchmark instances. Test results first show that our algorithm outperforms most existing approaches for the classical flexible job shop scheduling problem. Additional experiments also confirm the significant improvement achieved by integrating the propositions introduced in this study.

Introduction

In this paper, we address the job shop scheduling problem with flexible machines and sequence-dependent setup times. Scheduling refers to the allocation of resources to perform a set of tasks over a period of time. Under economic and commercial market pressures, developing an efficient and accurate schedule becomes increasingly important. Due to the wide applicability for real-world manufacturing systems, the Job shop Scheduling Problem (JSP) is one of the most popular scheduling problems. In the classical JSP, a set of jobs are to be processed on a set of given machines. Each job can be divided into operations, which are assigned to prescribed machines, and are processed according to specific technological orders.

Considering the growing demand on flexibility and reliability, several machines are often capable of performing similar tasks. Especially in Flexible Manufacturing Systems (FMS), a high machine flexibility is characteristic (Rossi, 2014). In this context, the availability of alternative resources can increase performance, and help to manage preventive maintenance or tackle breakdown and other unforeseen events. Taking this into account, the JSP can be extended to the Flexible Job shop Scheduling Problem (FJSP), where an operation can be carried out on a set of compatible machines. The FJSP was originally stated by Brucker and Schlie (1990). The routing flexibility of a job then results in two sub-problems: The assignment of each operation to a specific machine has to be decided and operations have to be sequenced on each machine to optimize a given criterion.

Moreover, setup times are another important characteristic of many practical real-world scheduling settings. The integration of setup times has a significant impact on the applicability and performance of scheduling algorithms for practical manufacturing systems (e.g., Krajewski, King, Ritzman, Wong, 1987, Wilbrecht, Prescott, 1969). Undeniable savings have also been observed when setup times are explicitly investigated in the scheduling decisions (Allahverdi, Ng, Cheng, & Kovalyov, 2008). Conventional studies of manufacturing lines, however, often focus on the operation time, and setup times are assumed to be zero or constant. In many real applications such as chemical, printing, pharmaceutical, and automobile manufacturing, setups are not only required between jobs but also strongly depend on the preceding process on the same machine. These facts motivate our study.

More precisely, we consider the flexible job shop scheduling problem with sequence-dependent setup times (FJSP-SDST) to minimize the makespan. Sequence dependency indicates that the magnitude of setup times is determined by the current job as well as the direct previous job processed on the same machine. As a generalization of the classical JSP, the FJSP-SDST is known to be strongly NP-hard (Garey, Johnson, & Sethi, 1976). According to Cheng, Gupta, and Wang (2000), the problem to be addressed here has comparatively higher complexity status. In fact, sequence-dependent setup times are generally regarded as one of the most difficult aspects of scheduling problems (Laguna, 1999). Exact solution methods are therefore not adapted to solve problems of large sizes, and our algorithm is developed based on tabu search techniques, which proved to be successful for the FJSP (see Dauzère-Pérès and Paulli (1997) and Mastrolilli and Gambardella (2000)).

Since the 1990s, the FJSP has been extensively investigated by researchers (e.g., Brandimarte (1993); Chen, Wu, Chen, and Chen (2012); Dauzère-Pérès and Paulli (1997); Jia and Hu (2014); Kacem, Hammadi, and Borne (2002); Mastrolilli and Gambardella (2000); Roshanaei, Azab, and ElMaraghy (2013)). A more general FJSP, referred to as general job shop problem, is considered by Dauzère-Pérès, Roux, and Lasserre (1998), Dauzère-Pérès and Pavageau (2003), Imanipour (2006) and Vilcot and Billaut (2008), where routings may be non linear (operations may have more than one predecessor and more than one successor). While Imanipour (2006) presents a non-linear MIP model as well as a hybrid greedy/tabu search algorithm with the makespan as the objective, Vilcot and Billaut (2008) study a bi-criteria optimization problem where both the the makespan and the maximum lateness are minimized. They develop a tabu search algorithm and an efficient genetic algorithm taking into account multiple constraints encountered in the printing and boarding industry. Dauzère-Pérès et al. (1998) extend the results and the approach in Dauzère-Pérès and Paulli (1997) to this problem but also to the case where operations may have to be processed on multiple resources. Dauzère-Pérès and Pavageau (2003) further extend this research to the case where an operation that needs multiple resources might not need all the resources during its entire processing time.

Regarding the FJSP with other extensions, Liu and MacCarthy (1997) discuss the problem arising in an FMS with transportation times and limited buffers. They propose a Mixed Integer Linear Programming model (MILP) and two heuristics to minimize the makespan as well as the mean completion time and the maximum tardiness. Mati, Lahlou, and Dauzère-Pérès (2011) propose a genetic algorithm for a practical FJSP in which blocking constraints are taken into account. Mousakhani (2013) presents an MILP as well as an iterated local search algorithm that minimize total tardiness.

For multi-criteria objectives, Guimaraes and Fernandes (2006) present a genetic algorithm. To simultaneously minimize the makespan and the mean tardiness, Bagheri and Zandieh (2011) develop a variable neighborhood search algorithm.

We next summarize publications addressing the FJSP with various types of setup times. A recent survey on scheduling with setups can be found in Allahverdi (2015). Saidi-Mehrabad and Fattahi (2007) take into account a special case of the FJSP where each operation can be assigned to one of two parallel machines. A tabu search algorithm that first solves the sequencing problem and then the assignment problem is developed. The algorithm is compared to a branch and bound algorithm for several random test instances. Defersha and Chen (2010) study the FJSP with attached and detached setup times, machine release dates, and technological time lag constraints. For this problem, an MILP is formulated, and a parallel genetic algorithm using multiple threads is introduced. Rossi and Dini (2007) solve a problem arising from a practical manufacturing environment with transportation times and overlapping of transportation times with processing times by an ant colony optimization method. Based on their previous study, Rossi (2014) discusses the FJSP with related parallel machines and setup times. An advanced ant colony optimization algorithm is applied to solve the assignment and sequencing problem in a single step. Transportation times, varying release dates for each job as well as an overlapping of transportation and processing times are included as well. For adjusted job shop benchmark instances, the proposed algorithm is compared to existing heuristics such as the genetic algorithm by Chan, Wong, and Chan (2006). Abdelmaguid (2015) considers special cases of the FJS-SDST. More precisely, the authors assume a symmetric definition of setup times and relative small setup times in relation to processing times. Under these conditions, structural properties are examined and formulated. The authors then extend the neighbourhood structure proposed in Mastrolilli and Gambardella (2000) which is proved to be viable.

Another stream of literature adds a third dimension to the FJSP by additionally considering process plan flexibility. Özgüven, Yavuz, and Özbakır (2012) optimize hierarchically the makespan and a balanced workload with an MILP model, which is an extension of the formulation of Özgüven, Özbakır, and Yavuz (2010). Both cases of separable as well as non-separable setup times are taken into account. Adding the no-wait restriction to the problem, Jolai, Rabiee, and Asefi (2012) develop a hybrid meta-heuristic. Assembly job shop systems with setups are considered in Nourali, Imanipour, and Shahriari (2012) and Nourali and Imanipour (2014). In these systems, each job is viewed as a final product and composed of multiple parts. Predecessor and successor relationships are predefined among parts of the same job. While Nourali et al. (2012) propose a mathematical model to integrate process planning and scheduling for assembly job shop systems, Nourali and Imanipour (2014) develop a particle swarm optimization algorithm.

Sharma and Jain (2015) consider the sequence dependent setup times in stochastic dynamic job shop system, where jobs arrive continuously over time and at least one parameter of the job settings is probabilistic. The authors present a simulation model to compare the performance of nine dispatching rules. Based on their previous study, Sharma and Jain (2016) develop four setup-oriented dispatching rules for a stochastic dynamic job shop. Simulation experiments show that the new rules outperform traditional dispatching rules.

González, Vela, Varela, and González-Rodríguez (2015) include non-anticipatory setup times in a flexible job shop environment and present a scatter search algorithm. This settings differ from most conventional setup definitions as they are attached to jobs and cannot be separated from processing time. Ortiz, Neira, Jiménez, and Hernández (2016) investigate a case study in Apparel industry which resembles the flexible job shop system with setups and transfer batches. A dispatching algorithm is presented to minimize average tardiness. Rohaninejad, Kheirkhah, Vahedi Nouri, and Fattahi (2015) considers a particular case of capacitated job shop problem with sequence dependent setup cost. An MIP model and two hybrid approaches are developed to minimize the sum of tardiness cost, overtime cost and setup cost.

Considering its complexity status and broad application, the flexible job shop problem with setup times still attracts significant attention from scheduling community. Intensified research for the FJSP-SDST is thus desirable. The remaining of the paper is organized as follows. To formulate the problem under study, a mathematical model is first presented in the next section. Section 3 introduces a representation based on a disjunctive graph. Section 4 elaborates the key elements of our tabu search algorithm. Computational results and analyzes are summarized in Section 5. Some conclusions and perspectives are provided in Section 6.

Section snippets

Problem description and MILP modelling

The FJSP-SDST can be stated as follows. A set J of n jobs and a set M of m machines are given. Each job i consists of a sequence of ni consecutive operations, where the jth operation of job i, denoted by Oij, can be processed on any machine among a subset MijM of compatible (also called eligible) machines.

For each operation Oij, let pijk be its processing time on machine kMij. Motivated by practical applications, we define setup times as both sequence and machine dependent. A setup time siik

Structural properties

To study the structural properties of the problem, we utilize the concept of disjunctive graphG=(O,A,E). Set O contains two fictitious nodes 0 and *, and each remaining node is associated with an operation: O={0,1,,o,*},which is decomposed into subsets containing operations of a single job. Subset Oi represents ni operations of job i indexed consecutively by Oi={li1+1,,li1+ni},where li=h=1inh is the total number of operations of the first i jobs, and h=1nnh=o holds.

For better

Tabu search algorithm

In order to thoroughly test the performance of our algorithm, we use a randomly generated initial solution. Key components of the algorithm include a neighborhood structure with feasibility checks and preliminary neighbor evaluations, a tabu list and a specific diversification.

Experimental design

Computational experimentation consists of four major parts:

  • 1.

    Comparing our MILP with the model presented in Saidi-Mehrabad and Fattahi (2007);

  • 2.

    Solving the classical FJSP without setup times, where test results are compared with those of eight existing approaches;

  • 3.

    Solving the FJSP with SDST, where

    • comparison of our MILP with our tabu search algorithm is conducted; and

    • comparison of our tabu search algorithm with two metaheuristics in the literature is conducted.

  • 4.

    Examining functionalities of our tabu

Conclusions

In this paper, we investigate the flexible job shop scheduling problem with sequence-dependent setup times. A mathematical model is first presented which is used in our numerical experiments. After studying structural properties based on a disjunctive graph model, we propose a tabu search algorithm with novel neighborhood functions and a specific diversification structure. Computational experiments are conducted on well-known benchmark instances. They show that our algorithm outperforms most

References (52)

  • LiuJ. et al.

    A global MILP model for FMS scheduling

    European Journal of Operational Research

    (1997)
  • C. Özgüven et al.

    Mathematical models for job-shop scheduling problems with routing and process plan flexibility

    Applied Mathematical Modelling

    (2010)
  • C. Özgüven et al.

    Mixed integer goal programming models for the flexible job-shop scheduling problems with separable and non-separable sequence dependent setup times

    Applied Mathematical Modelling

    (2012)
  • F. Pezzella et al.

    A genetic algorithm for the flexible job shop scheduling problem

    Computers and Operations Research

    (2008)
  • A. Rossi

    Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships

    International Journal of Production Economics

    (2014)
  • A. Rossi et al.

    Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method

    Robotics and Computer-Integrated Manufacturing

    (2007)
  • P. Sharma et al.

    Performance analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times: Simulation approach

    CIRP Journal of Manufacturing Science and Technology

    (2015)
  • G. Vilcot et al.

    A tabu search an a genetic algorithm for solving a bicriteria general job shop scheduling problem

    European Journal of Operational Research

    (2008)
  • M. Yazdani et al.

    Flexible job-shop scheduling with parallel variable neighborhood search algorithm

    Expert Systems with Applications

    (2010)
  • R. Battiti et al.

    The reactive tabu search

    ORSA Journal on Computing

    (1994)
  • P. Brandimarte

    Routing and scheduling in a flexible job shop by tabu search

    Annals of Operations Research

    (1993)
  • P. Brucker et al.

    Job-shop scheduling with multi-purpose machines

    Computing

    (1990)
  • ChanF. et al.

    Flexible job shop scheduling problem under resource constraints

    International Journal of Production Research

    (2006)
  • ChenH. et al.

    A genetic algorithm for flexible job shop scheduling

    Proceedings of the IEEE international conference on robotics and automation

    (1999)
  • ChengT. et al.

    A review of flowshop scheduling research with setup times

    Production and Operations Management

    (2000)
  • S. Dauzère-Pérès et al.

    An integrated approach for modelling and solving the general multiprocessor job-shop scheduling problem using tabu search

    Annals of Operations Research

    (1997)
  • Cited by (173)

    • The flexible job shop scheduling problem: A review

      2024, European Journal of Operational Research
    • Flexible job-shop scheduling with transportation resources

      2024, European Journal of Operational Research
    View all citing articles on Scopus
    View full text