Rescheduling for new jobs on single machine with locked initial jobs
GUO Yan-dong
GUO Jia-xi
LUN Shu-xian
Abstract：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.
Keywords：reschedulingsingle machinenew jobsNP-hard
Publication Date：2015-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：7( 168-174 )