Open AccessScheduling with lot streaming in a two-machine re-entrant flow shop
Author(s) -
Ferda Can Çetinkaya,
AUTHOR_ID,
Mehmet Duman,
AUTHOR_ID
Publication year - 2021
Publication title -
operational research in engineering sciences: theory and applications/operational research in engineering sciences: theory and applications.
Language(s) - English
Resource type - Journals
eISSN - 2620-1747
pISSN - 2620-1607
DOI - 10.31181/oresta111221142c
Subject(s) - job shop scheduling , flow shop scheduling , computer science , mathematical optimization , heuristic , scheduling (production processes) , upper and lower bounds , algorithm , artificial intelligence , mathematics , schedule , mathematical analysis , operating system
Lot streaming is splitting a job-lot of identical items into several sublots (portions of a lot) that can be moved to the next machines upon completion so that operations on successive machines can be overlapped; hence, the overall performance of a multi-stage manufacturing environment can be improved. In this study, we consider a scheduling problem with lot streaming in a two-machine re-entrant flow shop in which each job-lot is processed first on Machine 1, then goes to Machine 2 for its second operation before it returns to the primary machine (either Machine 1 or Machine 2) for the third operation. For the two cases of the primary machine, both single-job and multi-job cases are studied independently. Optimal and near-optimal solution procedures are developed. Our objective is to minimize the makespan, which is the maximum completion time of the sublots and job lots in the single-job and multi-job cases, respectively. We prove that the single-job problem is optimally solved in polynomial-time regardless of whether the third operation is performed on Machine 1 or Machine 2. The multi-job problem is also optimally solvable in polynomial time when the third operation is performed on Machine 2. However, we prove that the multi-job problem is NP-hard when the third operation is performed on Machine 1. A global lower bound on the makespan and a simple heuristic algorithm are developed. Our computational experiment results reveal that our proposed heuristic algorithm provides optimal or near-optimal solutions in a very short time.