并行可替换机床混合流程调度算法研究

针对并行机床混合流程调度特性，分析了两种可替换加工情况调度问题的特点，考虑到调度目标是使所有任务有两台并行机房上的加工时间跨度最小，在此基础上作出了两个相应的推理。推理1得出了一台同机床可以替换时的优化调度方法，推理2得出了两台机床都可以作为替换机床时的优化调度方法，并在分析定界法的基础上，给出了两台并行可替换机床两种情况下的优化调度算法，最后通过仿真实验证明了本算法的有效性。

A Method for Hybrid Flow-Shop Scheduling of Parallel Machines

Hybrid flow shop scheduling of parallel machines is a NP hard problem. Different from previous research which have two identical parallel machines at each stage, we for the first time studied the NP hard problem when the two parallel machines are not identical. The objective is to minimize the makespan. The branch and bound algorithm is employed. First, each job is assigned to one of the two machines which requires less time to complete the job, thus forming two job sequences. The time of the sequences which needs less time to complete is assigned as the lower bound. In section 3, we proposed two illations to re arrange the jobs so as to minimize the makespan. Simulation results as given in Table 1 show that our method can meet the requirement of real time scheduling.