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

项目名称： 大规模Job shop排序问题渐近最优算法研究

项目编号： No.11201282

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 顾满占

作者单位： 上海财经大学

项目金额： 22万元

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

中文关键词： 随机排序；时间表长；渐近最优；多代理；近似算法

英文摘要： 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 fina

英文关键词： stochastic scheduling；makespan；asymptotically optimal；multi-agent；approximation algorithm