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 − p0, T ] with T p0 and the job processing is of preemptive and resumable; (B) the MA is required in a relaxed time interval [0, T ] with T p0 and the job processing is of nonpreemptive; (C) the MA is required in a relaxed time interval [T0, T ] with 0 T0 T − p0 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 − (T0 + p0) 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

EB00000003621K

Available