新工件到达锁定初始调度的单机重调度问题

摘要

This paper studies that some new jobs come from some new orders need to be rescheduled by in-serting into initial schedule.Where, some initial jobs with release times in the initial schedule, and then the ini-tial schedule is locked.We consider two cases of this rescheduling problem, one is the new jobs with preemptive to be processed, another is the new jobs with non-preemptive.For the first case, a polynomial time algorithm is developed, and its optimality is proofed.For the second case, NP-hardness is proofed firstly, a heuristic is de-signed following, and then a special case is solved optimal by this heuristic , at last a characteristic of optimal so-lution is showed, The theoretical results of this research can solve practical problems of enterprise and enrich re-scheduling theory.%研究了新工件到达锁定初始调度的单机重调度问题。即有一组带有不同释放时间的初始工件已经按照最小化完成时间和的优化目标调度完毕，形成初始调度且已锁定，此时有一组释放时间为零的新工件到达，且需要插入初始调度进行加工，其优化目标为最小化新工件的完工时间和。文中研究了新工件的加工过程可中断和新工件的加工过程不可中断，共2类新工件到达锁定初始调度的单机重调度问题。分析了重调度问题的复杂性，针对第一类重调度问题提出了多项式算法并证明了其最优性。证明了第二类重调度问题为NP完全问题，提出了一个多项式算法，并证明了该算法的有效性和最优解的特征，解决了企业实际问题并进一步丰富了重调度理论。