期刊
COMPUTERS & OPERATIONS RESEARCH
卷 40, 期 1, 页码 438-450出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2012.07.015
关键词
Two-stage hybrid flow shop; Dedicated machine; Branch and bound; Makespan; Heuristic
类别
资金
- National Science Foundation of China [71101106, 71171149]
- NSFC major program [71090404/71090400]
This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines, in which the first stage contains a single common critical machine, and the second stage contains several dedicated machines. Each job must be first processed on the critical machine in stage one and depending on the job type, the job will be further processed on the dedicated machine of its type in stage two. The objective is to minimize the makespan. To solve the problem, a heuristic method based on branch and bound (B&B) algorithm is proposed. Several lower bounds are derived and four constructive heuristics are used to obtain initial upper bounds. Then, three dominance properties are employed to enhance the performance of the proposed heuristic method. Extensive computational experiments on two different problem categories each with various problem configurations are conducted. The results show that the proposed heuristic method can produce very close-to-optimal schedules for problems up to 100 jobs and five dedicated machines within 60 s. The comparisons with solutions of two other meta-heuristic methods also prove the better performance of the proposed heuristic method. (C) 2012 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据