摘要
针对混合流程调度的特性 ,研究了两台并行可替换机床的调度问题 .在一个加工阶段内有两台机床并可相互替代加工 ,调度目标是使所有任务在这两台机床上的加工时间最短 ,这个问题已被证明为NP hard问题 .为此在分枝定界算法基础上提出了两个关于调度替换原则的推理 ,作为解决这类调度问题的基本原则 .根据这两个推理给出了如何在这种混合流程调度中对任务排序及指定加工机床的启发式调度算法 。
This paper considers hybrid flow shop scheduling with two parallel machines at one stage, where a set of jobs needs processing on one of the two machines. Alternatives are available to allocate processors to process a job. Under a given alternative, a job is assigned to a specific processor, and requires correspondingly a specific processing time. Job preemption is not allows. To find a minimum makespan scheduling, which is strongly NP-hand, some efficient heuristics have been proposed in the literature. According to the characteristics of FMS, and based on the branch-and-bound algorithm, two theorems about the principle of alternatives are proposed. Furthermore, the heuristics scheduling algorithms about sequence and assigning the jobs on machines are developed for the hybrid flow-shop by using the two theorems. Finally, the computational experiments are conducted to illustrate the effectiveness of these algorithms. The heuristics scheduling algorithms are tested on problems with size of up to 120 jobs.
出处
《西安电子科技大学学报》
EI
CAS
CSCD
北大核心
2002年第1期35-38,共4页
Journal of Xidian University
基金
国家自然科学基金资助项目 (699840 0 4)
关键词
柔性制造系统
调度算法
计算机控制
Algorithms
Computer simulation
Machine tools
Scheduling