流水作业排序问题的在线算法设计与竞争比分析

排序问题是从实际生产中归纳出来的组合优化问题。流水作业排序是一种多阶段的排序问题，在供应链管理、生产和运输调度安排等实际问题中有着广泛的应用。有关流水作业排序及其推广问题的研究文献已经有很多，然而相应的在线排序问题研究却很少。本课题重点研究流水作业在线排序与带工件运输的在线排序问题。带工件运输的排序问题也可以看作一种两阶段流水作业排序。课题的主要研究内容包括多阶段流水作业在线排序、带运输车辆的单机在线排序、带配送时间的平行机在线排序、带配送时间的批处理机在线排序、带时间延迟的两阶段流水作业在线排序、带机器可用性限制的流水作业在线排序等问题。我们主要研究这些排序问题的下界、设计在线算法并进行竞争比分析。其中我们期望为前三个问题设计最优在线算法，为后面几个流水作业在线排序相关问题分析下界并设计较好的在线算法，希望这些研究成果能够为促进排序和组合最优化理论的发展做出贡献。

在本课题中，我研究了一类两阶段的流水作业排序问题及延伸问题。这些排序问题来自于制造业或供应链管理等实际问题。.我们研究第一个问题是经典的在线两阶段流水作业排序问题。有n个工件，每个有两个操作依次在两台机器上加工。工件是实时(over time)到达的。 加工过程中工件不允许中断。目标函数是既小化最后完工工件的完工时间。 我们设计了一个确定性的在线算法并证明了这个算法具有最好可能的竞争比1.618。 并且进一步，通过随机生成问题实例，我们进行了数据模拟试验。计算结果显示，这个在线算法所求的解在大多数情况下非常接近最优解。.第二个问题是两台同型机上带到达时间和运输时间的排序问题。有n个工件,每个工件由到达时间,加工时间和运输时间来刻画.有两个阶段. 在第一阶段中,n个工件需要安排在两台同型机上加工.在第二阶段, 每个工件一旦在机器上完工就立刻独立的运送到各自的目的地. 目标为极小化所有工件运送完的时间. 我们设计了一个在线算法,并证明了这个算法的竞争比为1.618..接下来的一个问题是m台批处理机上一个排序问题. 这也是一个两阶段排序问题. 每个工件由到达时间,加工时间和运输时间来刻画. K个工件可以组成一批在一台机器上加工, 批中工件具有相同的开始时间与完工时间, 批的加工时间由批中最长工件决定. 工件一旦完工立刻被运送到目的地. 我们设计了一个在线算法,并分析了算法的竞争比为r=1 + 1/u+1/v, 其中 u,v 是整数并且uv≤m. 当m趋近于无穷大时, 算法的竞争比趋向于1..我们也研究了两个两阶段的离线排序问题. 其中一个问题是单机上带一个不可用区间的排序问题. 另外一个是两台同型机上带一个不可用区间的排序问题. 这两个问题都含有工件的加工和运输两个阶段.我们对两个问题的不同情形,分别设计了启发式算法并分析了算法的最坏情况性能比..综合以上研究结果, 项目已经完成了5篇论文,其中2篇已在sci杂志正式出版发表,2篇已经接收. .另外,项目负责人参加了两次国际学术会议并作了口头报告. 项目负责人及其他成员参加了多次全国学术会议.