大规模Job shop排序问题渐近最优算法研究

Scheduling problem belongs to the area of combinatorial optimization, and scheduling problem comes from practical production. Job shop scheduling problem is a class of complex multi-stage scheduling problems. The study of these problem plays an important role in the fields such as the management of supply chain and the control of production and transportation. Until now, many results have been attained for the job shop scheduling problem, but the result in the corresponding on-line and random variants is limited. This subject focuses on job shop online scheduling, stochastic scheduling and stochastic online scheduling problems with the objective to minimize the makespan. We mainly try to design asymptotcally optimal algorithms for the problems above, including proving the asymptotical optimality of the algorithms and giving the numerical simulation experiments. Based on the known lower bounds, one of our aims is to devise an asymptotically optimal algorihtm for the general job shop online scheduling problems, with an addition optimality gap of order O(1). In addition, we expect to obtain lower bounds for the stochastic scheduling varant, and give an asymptotically optimal algorithm with a gap of lower order. For some special case, we hope to achieve a gap of order O(1). Building on the results achieved, we finally study job shop stochastic online scheduling, and look forward to some basic conclusions for this new varant. We expect that the research of this project could make contribution to the solution of practical problems and the development of scheduling theory.

排序问题是从实际生产中归纳出来的组合优化问题，异顺序作业（job shop）排序是一类复杂的多阶段排序问题，在供应链管理、生产和运输调度等实际问题中有着广泛的应用。有关job shop排序问题的研究成果已经很多，但相应的在线排序和随机排序的研究却很少。本课题重点研究job shop 在线排序、随机排序和随机在线排序问题，目标为最小化最大完工时间（makespan）。我们主要研究为上述问题设计渐近最优算法并给出理论证明和数值模拟实验。其中针对在线排序问题的一般情况，利用目前已有的下界，期望给出误差（gap）为O(1)的渐近最优算法；另外为随机排序问题分析函数值的下界并设计误差较小的渐近最优算法，对某些特殊情况深入研究，期望给出误差为O(1)的渐近最优算法；在此基础上，研究随机在线排序问题，期望得出一些初步结果。希望这些研究成果能够为解决实际问题和促进排序理论的发展做出贡献。

本项目研究组合优化领域中的排序问题。排序问题起源于二十世纪五、六十年代，作为运筹学的一个分支，主要研究如何完成若干项任务，而把所需要用到的人、财、物等资源按时间进行最优分配、最优排序和最优调度。近年来，由于受到生产调度和计算机控制系统等领域应用的推动，排序理论发展迅速，成果丰硕。本项目考虑若干排序问题，目标函数为时间表长（makespan）或其期望值。.首先考虑随机排序问题。对可中断随机排序问题，考虑加工机器为单机和m台同类机（uniform machines）的情形，基于Gittins index概念，给出子工件和元工件定义，由此得出最优函数值的下界，并设计渐近最优算法。对大规模job shop排序问题，建立流体松弛模型，并根据流体松弛模型最优解设计了原问题渐近最优算法并给出数值模拟实验。我们将该结果推广到了确定的job shop排序问题，其中加工机器类型包括批处理机、多台同型机（parallel machines）、带中断的处理机等。.另一方面，考虑近似算法求解多代理排序问题。首先针对g个代理的两台同型机排序问题，基于LPT规则，设计近似算法，并证明算法所得排序中第i个完工的代理，其makespan为该代理最优makespan的最多i+1/6倍，其中1/6为LPT规则求解经典问题P2||Cmax的误差上界，我们证明该性能比是紧的。该结果被推广到m台同型机情形，我们设计了近似算法，并证明所得排序中，第i个完工的代理，其makespan为该代理最优makespan的最多i+(1/3 -1/(3m))。此外，本项目还考虑两个代理的单机在线排序问题，目标函数为两个代理makespan的线性组合。对该问题，设计了近似算法，并分析该算法的性能比，在某些特殊情形下该算法的性能比达到原问题算法的下界。