论文部分内容阅读
本文研究的是带服务器的流水作业和自由作业排序问题，它们分别是经典流水作业和自由作业排序问题的推广，其中每个工件的每道工序在由机器加工之前都必须由一个服务器安装在一台机器上，而一个服务器在同一时间只能安装一个工件。本文主要研究了带一个服务器的两台机流水作业和自由作业排序问题，对以下两个问题设计了近似算法并分析了其最坏情况界。
本文首先讨论了安装时间均为s的两台机流水作业排序问题，目标是极小化工件的最大完工时间。该问题用三参数表示法可表示为如下形式：F2,S1|sij=s|Cmax。对该问题本文在经典的两台机流水作业排序问题的Johnson算法的基础上提出了近似算法，并证明了该算法的最坏情况界为3/2。
本文接下来讨论了安装时间均为1的两台机自由作业排序问题，目标是极小化最大完工时间。该问题用三参数表示法可表示为如下形式：O2,S1|sij=1|Cmax。对该问题本文在经典的两台机自由作业排序问题的双向排序法的基础上提出了近似算法，并证明了该算法的最坏情况界为3/2。