关键词: 流水车间, 调度, 零等待, 启发式算法

Abstract: To minimize the total flow time of a class of two-machine no-wait flowshop scheduling problem, a heuristic algorithm was proposed based on the structural information of the problem to obtain near-optimal solution. According this flowshop scheduling problem, an operation of a job on any machine consisted of three phases: setup, processing and removal. The setup and removal time were separated from the processing time. Optimization properties were first analyzed. Based on the analysis of optimization properties, the algorithm was constructed, which could provide near optimal solutions in a modest amount of computer time. The heuristic costs were compared with the optimal costs and lower bounds on the optimal costs for small-scale instances and large-scale instances separately. Extensive numerical test indicated the effectiveness of the proposed heuristic algorithm and demonstrated the potential capacity of the algorithm to solve large-scale problems.

Key words: flowshop, scheduling, no-wait, heuristic algorithm