Two-machine flowshop group scheduling problem
This paper considers a two-machine flowshop group scheduling problem. The jobs are classified into groups and the jobs in the same group must be processed in succession. Each group requires a set up time and removal time on both machines. A transportation time is required for moving the jobs from machine 1 to machine 2. The objective is to minimize the maximum completion time (makespan). A polynomial time algorithm is proposed to solve the problem. This generalizes the algorithms proposed by Baker and others. Recently, an important class of scheduling problem is characterized by a group scheduling constraint where the jobs are classified into groups by the same operation requirements or characters. Each group requires a setup time and removal time on both machines. That is, each machine needs a time to set up or to remove the tools, jigs and fixtures when the group starts processing or completes processing. A transportation time is required to move the jobs between the machines. The objective is to find a sequence of groups and jobs in each group such that the maximum completion time (makespan) is minimized. Baker provided an optimal algorithm for this problem in the case of two-machine flowshop group scheduling without considering the removal and transportation times. But, in some manufacturing environments, it is required to consider the group removal time and job transportation time. The main contribution of this paper is to develop a polynomial time algorithm, which generalizes the algorithms proposed by Baker and others.
two-machine flowshop group scheduling maximum completion time