考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.

This paper considers the distributed permutation flow shop scheduling problem with eligibility constraints, which means that there exists an available factory set for each job. The processing time of each job in different factories may not be the same. We present a mixed integer linear programming based on position of jobs in all factories. The general problem and three special cases are analyzed and several heuristic algorithms are proposed with performance guarantee. A heuristic algorithm based on greedy algorithm, LFJ and NEH is carried out to obtain an approximate solution. The branch and bound method based on the approximate value is proposed to find optimal scheduling. At last, an example is used to explain the computing process of NEHg2 and the branch and bound method; numerous experiments prove the effectiveness of the NEHg heuristics.