Equivalence of Some Different Maintenance Activities in Single-Machine Scheduling
- PDF / 438,371 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 198 Views
Equivalence of Some Different Maintenance Activities in Single-Machine Scheduling Juan Zou1,2 · Jin-Jiang Yuan1
Received: 3 June 2017 / Revised: 28 June 2017 / Accepted: 31 October 2017 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2017
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 − 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. Keywords Scheduling · Maintenance · Dynamic programming Mathematics Subject Classification 90B35 · 90C27
This research was supported by the National Natural Science Foundation of China (No.11671368) and the National Natural Science Foundation of Henan Province (No. 15IRTSTHN006). The first author was also supported by the National Natural Science Foundation of Shandong Province (NZR2017MA031).
B
Jin-Jiang Yuan [email protected] Juan Zou [email protected]
1
School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
2
School of Mathematical Sciences, Qufu Normal University, Qufu 273165, Shandong, China
123
J. Zou et al.
1 Introduction In the past decades, scheduling with machine availability had been a hot topic in scheduling research. For our purpose, we only consider the single-machine scheduling problem in which a maintenance activity (MA) of length p0 on the machine is required at a given time period. This means that the MA must be performed at some time interval of length p0 without interruption. 1.1 Problem Formulation According to the requirements for the MA and the features of the machine for processing jobs, the following three assumptions are studied in the literature, separately. Assumption (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. Moreover, we use ( A∗ ) to denote the assumption that the MA is required in a fixed time interval [T − p0 , T ], and the job processing is of nonpreemptive. Assumption (B) The MA is required in a relaxed time interval [0, T ] with T p0 , and the job processing is of nonpreemptive. In this case, [0, T ] is called the execution window of the MA. Assum
Data Loading...
