工件允许重启的在线排序研究

Online scheduling is an important research direction of Combinatorial Optimization. This project mainly studies online scheduling with jobs using restart or limited restart. In the online scheduling models studied in this project, the jobs arrive online over time, and the information of each job is unknown in advance until it is released. “Restart” means that a running task may be interrupted, losing all the work done on it. The jobs in the interrupted task are then released and become independently unscheduled jobs which can be scheduled anew later. “Limited restart” means that the maximum number for restarts of a job is limited. Allowing restart means that we have the chance to change our mind and make a better decision in view of the new information emerging from the newly arrived jobs. This project studies the online scheduling or semi-online scheduling with jobs using restart or limited restart, which include: scheduling on a parallel batch machine or m parallel batch machines to minimize the maximum delivery completion time of all jobs or the maximum completion time of all jobs; scheduling on a regular machine to minimize the maximum delivery completion time of all jobs. This project tries to derive some innovative contributions from the following two aspects: On one hand, getting the lower bound of the problems, namely, the best performance among all online algorithms’; On the other hand, using the methods such as delay method, multiple method, greedy method to design and analyze best possible online algorithms matching the established lower bounds.

在线排序是组合最优化领域的重要研究方向。本项目主要研究工件允许重启或有限重启的在线排序问题。其中在线指工件依时间在线到达，工件的信息只有在其到达后才能释放出来。而工件允许重启指正在加工的工件或工件批可以中断，中断加工的工件被重新释放出来(对这些工件之前加工作废) 再重新安排加工。而有限重启指每个工件的最大重启次数有限制。工件允许重启意味着可以根据新到工件的信息对原先生成的排序进行修正，故而可以得到更优的排序。本项目所研究的工件允许重启或有限重启的在线排序问题主要包括：单台或m台平行批处理机上的目标函数为最小化最大运输完工时间或最大完工时间的排序问题；一般机器上的目标函数为最小化最大运输完工时间的排序问题。本项目力求取得若干创新性结果：一、分析出问题的下界，即在线算法的性能最好能达到什么值。二、借助于延迟法、倍数法、贪婪法等方法设计与下界相匹配的最好可能的在线算法。

在线排序是组合最优化领域的重要研究方向。工件允许重启或有限重启的在线排序问题的价值在于工件允许重启时往往可以得到比不允许重启时更好的在线算法，从而得到更好的排序或生产计划。本项目主要对工件有限重启时的考虑运输的平行批处理上的在线排序问题进行了研究，同时对于drop-line平行批处理机上的相应问题进行了研究，目标函数是最小化最大运输完工时间。本项目对以上问题进行了系统的研究，并对其中多个问题得到了最优在线算法。受本项目资助共发表学术期刊论文4篇，其中SCI论文3篇，核心1篇。另最近有一篇论文被SCI期刊接收。代表性成果如下：（1）研究了工件允许有限重启的单台平行批处理机上（或单台drop-line平行批处理机上）目标是最小化最大运输完工时间的在线排序问题，其中加工时间和运输时间具有一致性。这里的一致性是指对于任意两个工件，加工时间较大的工件其运输时间不小于加工时间较小的工件的运输时间。我们对该问题给出了最好可能的在线算法。（2）研究了工件允许有限重启的单台平行批处理机上目标是最小化最大运输完工时间的在线排序问题，其中每个工件的运输时间不大于其加工时间，对该问题给出了最好可能的在线算法。（3）研究了工件允许有限重启的单台drop-line平行批处理机上目标是最小化最大运输完工时间的在线排序问题，对该问题得到了最好可能的在线算法。（4）研究了工件允许有限重启的单台drop-line平行批处理机上目标是最小化最大运输完工时间的在线排序问题，其中每个工件的运输时间不大于其加工时间，对该问题得到了最好可能的在线算法。