Heuristic algorithms for re-entrant hybrid flow shop scheduling with unrelated parallel machines

This paper considers the scheduling problem in hybrid flow shops with parallel machines at each serial production stage. Each job may visit each stage several times, called the re-entrant flows. As an extension of the research on generic re-entrant hybrid flow shop scheduling, the unrelated parallel machines at each stage are considered and hence the processing time of a job at each stage depends on the machine where the job is processed. The problem is to determine the allocation of jobs to the unrelated parallel machines as well as the sequence of the jobs assigned to each machine for the bicriteria objectives of minimizing makespan and total tardiness. Since due dates must be satisfied after being negotiated with customers in most practical situations, the original problem is transformed into a problem with a single objective of minimizing makespan by moving the tardiness objective to a constraint set with a certain allowance. Because of the complexity of the problem, two heuristic algorithms are suggested and tested in this paper. In particular, the performances of the heuristics are shown with the gaps from the solution values obtained from a search heuristic with a sufficiently long computation time.