柔性制造系统调度算法研究

针对混合流程调度的特性，研究了两台并行可替换机床的调度问题，在一个加工阶段内有两台机床并可相互替代加工，调度目标是使所有任务在这两台机床上的加工时间最短，这个问题已被证明为NP-hard问题。为此在分枝定界算法基础上提出了两个关于调度替换原则的推理，作为解决这类调度问题的基本原则。根据这两个推理给出了如何在这种混合流程调度中对任务排序及指定加工机庆的启发式调度算法，最后，通过仿真试验验证了该算法的有效性。

Research on the scheduling algorithms of FMS

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 hard, 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 nachines 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 is tested on problems with size of up to 120 jobs.