以NP-难的最小化时间表长为目标的混合流水车间调度问题为研究对象.把工件在第1阶段开始加工的排序问题转化为旅行商问题,采用蚁群系统求得初始排序；在第1阶段后各阶段采用工件先到先服务规则选择工件、最先空闲机器优先规则选择机器以构建初始工件的机器指派与排序；充分利用已知的机器布局和工件加工时间特点,确定工件加工瓶颈阶段,并以此为基础对工件的机器指派与排序进行改进.用Carlier和Neron设计的Benchmark算例仿真后与著名的NEH算法比较,表明这种算法是有效的.%The scheduling problem of hybrid flow shop with makespan as objective is discussed. In a hybrid flow shop, there are multiple machines at each stage and its scheduling problem is known to be NP-hard. A new method is proposed in this paper. By the proposed method, for the first stage, the job sequencing is formulated as a traveling salesman problem and the ant colony method is used to solve it. For the following stages, dispatching rules, such as first come first served and first available machine first, are used to obtain an initial solution. Then, the initial solution is improved by identifying the bottleneck stage in taking the advantage of knowledge about job processing times and machine configurations. To evaluate the performance of the proposed algorithm, it is tested by using the Carlier and Neron's benchmark problems. It is shown that proposed method is effective and outperforms the well-known Nawaz-Enscore-Ham (NEH) heuristic.
展开▼
