MINIMIZING THE MAKESPAN IN THE TWO-MACHINE FLOWSHOP SCHEDULING PROBLEM WITH AN AVAILABILITY CONSTRAINT

摘要

This paper studies a two-machine flowshop scheduling problem with an availability constraint. Contrary to most literature where machines are available at all times, we assume that a machine may not always be available. The problem is very important, as it happens often in the industry. For example, a machine may not be available in the scheduling period due to a breakdown or preventive maintenance. Also if a machine continues to process those unfinished jobs that were scheduled in the previous planning period, then it is not available at the beginning of the period. We study the problem under a deterministic environment. Namely, we assume that the unavailable time is known in advance. We prove that the problem is NP-hard. We then develop pseudo-polynomial dynamic programming algorithm to solve the problem optimally. We also provide heuristic algorithms with an error bound analysis. In particular, we propose two O(n log n) time heuristic algorithms. The first heuristic is used to solve the problem with an availability constraint imposed on machine 1, and has a worst case error bound of 1/2. The second heuristic is used to solve the problem with an availability constraint imposed on machine 2, and has a worst case error bound of 1/3. We note that the problem is not reversible, in the sense that interchanging job processing time on machine 1 and 2 will not yield an equivalent problem, which is different from the standard flowshop problem. (C) 1997 Elsevier Science B.V. [References: 17]