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

doi:10.1016/0360-8352(94)00026-J

Computers & Industrial Engineering

Volume 28, Issue 1, January 1995, Pages 63-70

https://doi.org/10.1016/0360-8352(94)00026-J Get rights and content

Abstract

We consider a two-machine flowshop sequencing problem with limited waiting time constraints. This means that for each job the waiting time between two machines cannot be greater than a given upper bound. The objective is to minimize the makespan. There are efficient algorithms for the special cases of infinite waiting time and zero waiting time. The two-machine flowshop sequencing problem with limited waiting time constraints is shown to be NP-hard. A branch-and-bound algorithm is proposed, and computational experiments are provided.

References (8)

I. Adiri et al.
Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times
Naval Res. Logist. Q.
(1982)
S.S. Reddi et al.
On the flowshop sequencing problem with no wait in process
Opl Res. Q.
(1972)
A. Hodson et al.
A microcomputer based solution to a practical scheduling problem
J. Opl Res. Soc.
(1985)
A.H.G. Rinnooy Kan
Machine Scheduling Problems: Classification, Complexity and Computations
(1976)

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

Cited by (78)

Real-time admission control in a queue-time loop production system
2021, Computers and Industrial Engineering
The typical flow shop production system with queue time constraints consists of a queue-time loop with multiple stages and a limit on queue time between two consecutive stages. This paper proposes a mixed integer linear programming (MILP) model to address the dynamic environment such as job arrivals and machine failures of the production system. We determine the admission control decision at each stage in a queue-time loop and then reschedule the production after the real-time status of job arrivals and machine availability are updated. The combinatorial Benders’ cuts (CBC) is used to solve the MILP model which decomposes the variables into integer and continuous parts. In order to reduce the model’s size, the phase-step method (PS) is proposed and then is combined with the CBC, called CBC-PS method. Further, the production schedule of a multistage queue-time loop is generated. We find that the CBC-PS method can reduce up to 39.1% of the number of scrap jobs compared to first-in-first-out (FIFO), threshold dispatching (TH), and reaction chains (RC) heuristics.
Data analytics for time constraint adherence prediction in a semiconductor manufacturing use-case
2021, Procedia CIRP
Semiconductor manufacturing represents a challenging industrial environments, where products require more than several hundred operations, each representing the technical state-of-the-art. Products vary greatly in volume, design and required production processes and, additionally, product portfolios and technologies change rapidly. Thus, technologically restricted rapid product development, stringent quality related clean room requirements and high precision manufacturing equipment application enforce operational excellence, in particular time constraints adherence. Product specific time constraints between two or more successive process operations are an industry-specific challenge, as violations lead to additional scrapping or reworking costs. Time constraint adherence is linked to dispatching and currently manually assessed. To overcome this error-prone manual task, this article presents a data-based decision process to predict time constraint adherence in semiconductor manufacturing. Real-world historical data is analyzed and appropriate statistical models and scoring functions derived. Compared to other relevant literature regarding time constraint violations, the central contribution of this article is the design, generation and validation of a model for product quality-related time constraint adherence based on a real-world semiconductor plant.
A comprehensive review of Branch-and-Bound algorithms: Guidelines and directions for further research on the flowshop scheduling problem
2020, Expert Systems with Applications
This article is a comprehensive review of Branch-and-Bound algorithms for solving flowshop scheduling problems, from the early works of Ignall and Schrage (1965) and Brown and Lomnicki (1966) to the recent approaches of Labidi et al. (2018) and Li et al. (2018). The first part of the article contains an overview of the Branch-and-Bound algorithm, how it is applied for scheduling problems and its different components. The literature review is focused on permutation flowshop problems, and shows the contribution of each article to the method itself and its application. The articles are divided according to the characteristics of the problem and summarized in tables for an easier viewing. The objectives of this review are to provide guidelines for future research in the application of the Branch-and-Bound algorithm for scheduling problems and also to be used as an index for authors to locate the articles for particular problems within the state-of-the-art literature.
Minimizing the makespan in a flow shop environment under minimum and maximum time-lag constraints
2019, Computers and Industrial Engineering
This paper considers the flow shop scheduling problem with minimum and maximum time-lag requirements. According to the time-lag constraints, the starting time of each operation of a job must be within a specified time-window after the completion of its previous operation. The considered objective function is makespan and the problem is strongly NP-hard. In this article, a mixed integer linear programming (MILP) and two constraint programming (CP) models are proposed for the problem. To deal with the larger instances of this problems, it is decomposed into a sequencing and a timetabling sub-problem. A tabu search (TS) is developed to handle the sequencing sub-problem. Furthermore, an exact method based on the developed MILP as well as a greedy algorithm are proposed to deal with the timetabling sub-problem. A large number of test cases with different time-lag settings are solved to assess the performance of the proposed algorithm. Computational results confirm that the proposed TS is efficient and competitive. Moreover, the greedy timetabling method proves to be significantly faster than the exact method without sacrificing the solution quality.
Three-machine flow shop scheduling with overlapping waiting time constraints
2019, Computers and Operations Research
In this paper, we examine a three-machine flow shop scheduling problem with overlapping waiting time constraints with the objective of minimizing makespan. In the problem, jobs that finish processing on the first machine must be processed on the second and third machines within designated time periods. These overlapping waiting time constraints are common scheduling requirements in semiconductor manufacturing since up to 20% of all process steps are controlled with waiting time limits to achieve better quality. We first derive dominance properties for the problem by analyzing overlapping waiting time constraints, and then we develop a branch and bound algorithm that uses these properties. An initial solution is obtained by heuristic algorithms, and seven lower bounds are proposed for the branch and bound algorithm. The performance of the algorithm is evaluated with computational tests.
Permutation flowshop scheduling with time lag constraints and makespan criterion
2018, Computers and Industrial Engineering
A permutation flowshop with time lag constraints requires that the time lag between consecutive operations of a job must be in the given interval. In this study, the scheduling of such flowshop with makespan minimization objective is investigated. We prove that this problem has the reversibility property, and present a two-stage constructive heuristic with time complexity O(n²m), where n and m are the numbers of jobs and machines, respectively. The first stage generates a rank of jobs based on an equivalent formulation of the makespan, and the second stage constructs a schedule through an insertion mechanism. We apply the reversibility property to reduce the time complexity of insertion procedures in both two stages, and find a better solution by solving both the original problem and its reversed problem. To verify the effectiveness and efficiency of this heuristic, we compare its performance to the mixed integer linear programming (MILP) formulation of this problem for small-scale problems, and conduct a comprehensive computational study on the Taillard’s benchmark.

View all citing articles on Scopus

View full text

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

Abstract

Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times

Naval Res. Logist. Q.

On the flowshop sequencing problem with no wait in process

Opl Res. Q.

A microcomputer based solution to a practical scheduling problem

J. Opl Res. Soc.

Machine Scheduling Problems: Classification, Complexity and Computations