Abstract:

We study single-machine scheduling problems with a single maintenance activity (MA) of length p0 under three types of assumptions: (A) the MA is required in a fixed time interval [T−p₀,T ] with T⩾p₀ and the job processing is of preemptive and resumable; (B) the MA is required in a relaxed time interval [0, T] withT⩾p₀ and the job processing is of nonpreemptive; (C) the MA is required in a relaxed time interval [T₀,T]with 0⩽T₀⩽T−p₀ and the job processing is of nonpreemptive. We show in this paper that, up to the time complexity for solving scheduling problems, assumptions (A) and (B) are equivalent, and moreover, if T−(T₀+p₀) is greater than or equal to the maximum processing time of all jobs, the assumption (C) is also equivalent to (A) and (B). As an application, we study the scheduling for minimizing the weighted number of tardy jobs under the above three assumptions, respectively, and present corresponding time-complexity results.

Key words: Scheduling ·, Maintenance ·, Dynamic programming