Series production in a basic re-entrant shop to minimize makespan or total flow time

Series production in a basic re-entrant shop to minimize makespan or total flow time

0.00 Avg rating0 Votes
Article ID: iaor20101800
Volume: 58
Issue: 2
Start Page Number: 257
End Page Number: 268
Publication Date: Mar 2010
Journal: Computers and Industrial Engineering
Authors: , ,
Abstract:

This paper addresses a real life shop scheduling problem in a manufacturing company. In this problem, a set of n identical jobs are to be processed on two machines. Every job visits one of the machines more than once. This is therefore a re-entrant shop. Due to the fact that the jobs are identical, the decision version of this problem is even not in the class NP. We give an optimal schedule to minimize the makespan. Since the total flow time depends on the relations between the processing times, we decompose this problem into sub-problems according to the relations between the processing times. We prove various properties of optimal solutions and, based on these properties, we provide an optimal solution for all the sub-problems except one of them. For the sole remaining sub-problem, we prove a dominance property which allows to consider a part of schedules to find an optimal one.

Reviews

Required fields are marked *. Your email address will not be published.