机器带不可用时间限制的供应链排序问题研究

In the supply chain scheduling problem, processing and delivery of jobs are integrated to be considered. And the processing machine is always regarded as being available in the most of literatures. However, in the real manufacturing environments, the machine could be unavailable during some time interval because of maintenance etc. Therefore, we focus on the supply chain scheduling problem with unavailability constraints on the machine. Our goal is to obtain the optimal schedule by arranging the processing and delivery of jobs. We mainly study the offline problems concerned with the semi-resumable jobs, uncertain processing time of jobs, multiple customers or multiple unavailable time intervals on the machine and so on. For these problems, we try to discuss their computational complexities, and to design polynomial time optimal algorithms or approximation algorithms. Meanwhile, we develop algorithms for some online or semi-online problems and analyze the competitive ratio of those algorithms. As for this research originates from the management of the practical supply chain, the expected result is of great theoretical and practical significance.

供应链排序问题将工件的加工与发送结合起来进行研究。在大多数模型中，加工机器默认是一直可用的。然而在现实生产中，生产商经常要对机器进行维护，从而造成机器在某个时间段内不可用。如何安排工件在带不可用时间限制的机器上加工，完工后分批发送给客户，使相关目标达到最优，即为机器带不可用时间限制的供应链排序问题。我们主要研究不同情形下的离线问题，包括工件加工可部分继续、工件的加工时间不确定、多客户以及机器带多个不可用时间限制等。针对这些离线问题，我们分别讨论问题的计算复杂性，设计多项式时间的最优算法、或近似算法等。同时，对于一些在线、半在线问题，我们设计算法并进行竞争比分析。本项目的研究内容源于实际，研究成果必将对实际生产活动具有指导意义和实用价值。

供应链排序问题将工件的加工与发送结合起来进行研究。在大多数模型中，加工机器默认是一直可用的。然而在现实生产中，生产商经常要对机器进行维护，从而造成机器在某些时间段内不可用。如何安排工件在带不可用时间段的机器上加工，完工后分批发送给客户，使得与发送时间相关的目标达到最优，即为机器带不可用时间段的供应链排序问题。我们主要研究不同情形下的离线问题，包括工件加工可部分继续、工件的加工时间不确定、多客户以及机器带多个不可用时间段等。针对这些离线问题，我们分别讨论问题的计算复杂性，设计多项式时间的最优算法、或近似算法等。同时，对于一些在线、半在线问题，我们设计算法并进行竞争比分析。. 本项目的主要结果有：（1）对于工件的加工时间不确定的问题，我们证明问题是NP-难的，提出了伪多项式时间的动态规划算法，并设计了完全多项式时间近似方案(FPTAS)。（2）对于多个客户的问题，当工件的加工可继续时，我们就运输工具直接发送及选路线发送工件两种情形，分别提出动态规划算法得到最优发送序；当工件的加工不可恢复时，我们就运输工具直接发送及选路线发送工件两种情形，分别提出近似算法，并证明了算法的性能比。（3）对于源于医院实际情况的供应链排序问题，我们将问题转化为双任务排序问题以及三阶段的供应链排序问题，分析了问题的性质，并分别提出伪多项式时间的动态规划算法以及近似算法。（4）对于单机分批排序问题，我们对于最小化误工工件个数的目标，提出一个多项式时间最优算法；对于最小化总延误的目标，提出一个伪多项式时间的动态规划算法。对于合作排序博弈问题，我们证明问题是NP-难的，给出伪多项式时间的动态规划算法及两个近似算法。（5）对于在线、半在线问题，分别给出问题的下界，设计算法，并努力完成算法竞争比的证明。本项目的研究内容源于实际，研究成果必将对实际生产活动具有指导意义和实用价值。