CAJ | 학술논문

研究了新工件到达锁定初始调度的单机重调度问题。即有一组带有不同释放时间的初始工件已经按照最小化完成时间和的优化目标调度完毕，形成初始调度且已锁定，此时有一组释放时间为零的新工件到达，且需要插入初始调度进行加工，其优化目标为最小化新工件的完工时间和。文中研究了新工件的加工过程可中断和新工件的加工过程不可中断，共2类新工件到达锁定初始调度的单机重调度问题。分析了重调度问题的复杂性，针对第一类重调度问题提出了多项式算法并证明了其最优性。证明了第二类重调度问题为NP完全问题，提出了一个多项式算法，并证明了该算法的有效性和最优解的特征，解决了企业实际问题并进一步丰富了重调度理论。
연구료신공건도체쇄정초시조도적단궤중조도문제。즉유일조대유불동석방시간적초시공건이경안조최소화완성시간화적우화목표조도완필，형성초시조도차이쇄정，차시유일조석방시간위령적신공건도체，차수요삽입초시조도진행가공，기우화목표위최소화신공건적완공시간화。문중연구료신공건적가공과정가중단화신공건적가공과정불가중단，공2류신공건도체쇄정초시조도적단궤중조도문제。분석료중조도문제적복잡성，침대제일류중조도문제제출료다항식산법병증명료기최우성。증명료제이류중조도문제위NP완전문제，제출료일개다항식산법，병증명료해산법적유효성화최우해적특정，해결료기업실제문제병진일보봉부료중조도이론。
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.