A two-machine flowshop with unavailability interval on the second machine

摘要

The paper studies a two-machine flowshop with unavailability interval on the second machine. Contrary to most literature where machines are available at all times, this means that the machine may not always be available during the scheduling period, it needs a constant time to maintain the machine after completing a fixed number of jobs at most. The objective is to find the optimal job schedule such that the makespan is minimized. We focus on the relationship between the solution and the Johnson rule, and the performance of the Johnson rule as a heuristic when the job is resumable, analysis the worse-case performance ratio of the Johnson rule as a heuristic. Demonstrate the complexity of the problem when the job is nonresumable.