Permutation flowshop scheduling problems with maximal and minimal time lags

https://doi.org/10.1016/j.cor.2004.11.006Get rights and content

Abstract

In this paper, we study permutation flowshop problems with minimal and/or maximal time lags, where the time lags are defined between couples of successive operations of jobs. Such constraints may be used to model various industrial situations, for instance the production of perishable products. We present theoretical results concerning two-machine cases, we prove that the two-machine permutation flowshop with constant maximal time lags is strongly NP-hard. We develop an optimal branch and bound procedure to solve the m-machine permutation flowshop problem with minimal and maximal time lags. We test several lower bounds and heuristics providing upper bounds on different classes of benchmarks, and we carry out a performance analysis.

Introduction

The flowshop scheduling problem with time lags that we consider here can be formulated as follows: there are n jobs to be scheduled for processing on m machines. Each job has to be processed on each of the machines 1,2,,m visiting them in this order. The processing of job j on machine k requires pj,k0 time units. Preemption is not allowed, so that once a job has been started on a machine, it cannot be interrupted. Each machine can process at most one job at a time. For each job, minimal and maximal time lags between every couple of successive operations are required. Thus, the waiting time between two consecutive operations of the same job must be greater than or equal to a non-negative value θmin (minimal time lag) and smaller than or equal to a non-negative value θmax (maximal time lag) where θmaxθmin. There are several ways to define such lags, for instance we can consider the gap between the starting time of the job on the upstream machine and its starting time on the downstream machine (start-start lag). Similarly, stop-stop and stop-start lags may be considered. In this paper, we consider stop-start lags, but it is quite obvious to note that the resulting problems are equivalent, because processing times are known and deterministic. Therefore, we use simply the term time lags in this paper.

Given a sequence of jobs, we denote by cj,k the completion time of job j on machine k(j=1,2,,n;k=1,2,,m). If job j finishes on machine k-1 at cj,k-1 then j can start on machine k at tj,k such that tj,kcj,k-1+θj,k-1min and tj,kcj,k-1+θj,k-1max where θj,k-1min (resp. θj,k-1max) is the minimal (resp. maximal) time lag of job j between machines k-1 and k. The objective is to find a schedule such that the completion time of the last job is minimized.

Motivation for the formulated problem comes from industrial applications. Maximal time lags may be used to model situations when the delay between operations must not be too long in order to avoid deterioration of the products. In farm-produce industry involving perishable products, once the food has been prepared and cooked, it must be chilled before a certain amount of time has elapsed, otherwise it must be discarded [1]. Such constraints also arise in the field of biotechnologies and chemistry. For instance, the extraction of specific blood components from live blood cells require sterile conditions and the risk of contamination is likely to increase when the waiting time becomes too large.

Minimal time lags arise when waiting times between operations are imposed. Chu and Proth [2] study the case of an automated medical laboratory in which various analyses are performed. The durations of chemical reactions are lower and upper bounded, whereas the handling operations (introducing elements in the test tube, reading the results of the analyses) have fixed processing times. Therefore, the latter operations are considered as usual operations and the reactions are modelled with minimal and maximal time lags.

An example of permutation flowshop arises in hot metal rolling industries where ingots have to be processed continuously through the stages of the shop. Due to some technological constraints, job overpassing is not permitted and only permutation schedules are allowed.

Moreover, depending on the shapes and physical characteristics of the products, some operations require different levels of temperature to be performed. In order to reach these temperature levels, the ingots may be cooled down or heated. Therefore, waiting times between the stages may be upper and/or lower bounded. This corresponds to maximal and minimal time lags respectively. Deppner [3] presents other industrial examples and case studies of shop problems with such constraints.

Flowshop and open shop problems with two machines involving minimal time lags have been studied by Brucker et al. [4], who give complexity results for various criteria. Dell’Amico [5] focuses on the makespan minimization in two-machine flowshop and jobshop with minimal time lags and presents a tabu search approach. Yu [6], [7] studies the complexity of particular cases of the two-machine flowshop problem with minimal time lags. Only very few papers deal with shop scheduling problems with maximal time lags. Yang and Chern [8] consider a two-machine permutation flowshop problem.

The rest of the paper is organized as follows: Section 2 gives an overview of complexity and dominance results for two-machine problems, completed with new results. The remaining sections deal with the m-machine case: in Section 3 we consider the restricted problem of determining an optimal schedule for a fixed job sequence, in Section 4, a branch and bound procedure is described to minimize the makespan, in Section 5, some computational results are discussed. The article ends on concluding remarks about further research.

Section snippets

Two machines

In this section we consider the two-machine problem. Each job j has one minimal time lag θjmin and one maximal time lag θjmax. We consider respectively problems with only minimal time lags, with only maximal time lags, and involving both minimal and maximal time lags.

m-machine problem

As pointed in Section 2.3, the two-machine permutation flowshop problem with minimal and maximal time lags is strongly NP-hard, consequently the corresponding m-machine problem is also strongly NP-hard. We only consider permutation schedules, for which the order of the jobs is the same on the m machines. Due to maximal time lag constraints, the classical left-shifted schedules (for which these constraints are not taken into account) are not feasible. This leads to the following problem.

Branch and bound procedure

We develop here a branch and bound method for the m-machine permutation flowshop problem with minimal and maximal time lags. Branch and bound procedures are commonly used to solve exactly NP-complete problems. These are enumerative methods for which some elimination criteria are applied, so that unworthy subsets of the solution set are not considered in the search for an optimal solution. Each subset is evaluated with a lower bound on the best solution it may contain and if this lower bound is

Computational results

A computational experiment was conducted to evaluate the performance of the proposed solution procedure. The algorithms were coded in Visual Basic, and the computational experiments were run on a PC Pentium, 1200 MHz.

Conclusion

In this paper, we derived new complexity results for some flowshop scheduling problems with minimal and maximal time lags: most cases are NP-Hard, even for two machines. We also developed a branch and bound to solve to optimality the general m-machine permutation problem. Several lower bounds were implemented and tested, and some constructive heuristics were adapted to the particular constraints of the problem, to provide initial upper bounds. The instance generation scheme took different

References (18)

  • D.L. Yang et al.

    A two-machine flowshop sequencing problem with limited waiting time constraints

    Computers and Industrial Engineering

    (1995)
  • M. Nawaz et al.

    A heuristic algorithm for the m-machine, n-job flow shop sequencing problem

    Omega

    (1983)
  • A. Hodson et al.

    A microcomputer based solution to a practical scheduling problem

    Journal of the Operational Research Society

    (1985)
  • C. Chu et al.

    Single machine scheduling with chain structured precedence constraints and separation time windows

    IEEE Transactions on Robotics and Automation

    (1996)
  • Deppner F. Ordonnancement d’atelier avec contraintes temporelles entre opérations. PhD thesis, Institut National...
  • P. Brucker et al.

    Complexity results for flow-shop and open-shop scheduling problems with transportation delays

    Annals of Operations Research

    (2004)
  • M. Dell’Amico

    Shop problems with two machines and time lags

    Operations Research

    (1996)
  • Yu W, The two-machine flow shop problem with delays and the one-machine total tardiness problem. PhD thesis, Technische...
  • W. Yu et al.

    Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard

    Journal of Scheduling

    (2004)
There are more references available in the full text version of this article.

Cited by (0)

View full text