برنامه ریزی تک ماشینی با مدت زمان نگهداری وابسته به حجم کاری  On single-machine scheduling with workload-dependent maintenance duration

1 Introduction Scheduling with machine maintenance has been extensively investigated in recent years. According to the maintenance duration, research literatures in this area can be classified into two classes, i.e., the fixed maintenance duration and the variable maintenance duration. For the fixed maintenance duration, it is assumed that the duration of a maintenance activity is a fixed time length. There are so many research articles which contribute this topic. We refer the readers to the latest survey paper [8]. For the variable maintenance duration, Kubzin and Strusevich [3] were the first pioneers that considered the scheduling problems with variable maintenance duration. They investigated the makespan minimization problem in a two-machine flow shop and a two-machine open shop. They showed that the open shop problem is polynomially solvable for quite general functions defining the maintenance duration while the flow shop problem is binary NP-hard and pseudo-polynomially solvable by dynamic programming. Furthermore, they presented a fully polynomial time approximation scheme (FPTAS) and a fast 3/2-approximation algorithm for this problem. Xu, Sun, and Li [9] investigated the parallel machine scheduling problem with almost periodic maintenance and non-preemptive jobs to minimize makespan. Xu, Yin, and Li [10] considered two scheduling problems with machine maintenance under the assumption that the maintenance duration is an increasing linear function of the total processing time of the jobs that are processed after the machine’s last maintenance activity. The first problem concerns parallelmachine scheduling to minimize the completion time of the last finished maintenance, where the length of the time interval between any two consecutive maintenance activities is between two given positive numbers. The second problem deals with single-machine scheduling to minimize the completion time of the last finished job, where the length of the time interval between any two consecutive maintenance activities is fixed. They proposed two approximation algorithms for the considered problems and analyzed their performances. Bock, Briskorn and Horbach [1] studied a single-machine scheduling problem that integrated machine deterioration, where the current maintenance state of the machine is determined by a maintenance level which drops by a certain, possibly job-dependent, amount when jobs are processed. A maintenance level of less than zero is associated with the machine’s breakdown and is therefore forbidden. Consequently, maintenance activities that raise the maintenance level again may become necessary and have to be scheduled additionally. Two general types of maintenance activities are introduced. In the full maintenance case, maintenance activities are always executed until the machine has reached the maximum maintenance level. In contrast to this, the schedule in the partial maintenance case has to additionally determine the duration of maintenance activities. By combining both cases with regular objective functions such as minimization of maximum tardiness, minimization of the sum of completion times, or minimization of the number of tardy jobs, they analyzed the computational complexity of general and some specific cases. Luo, Cheng and Ji [7] addressed the problem of scheduling a maintenance activity and jobs on a single machine, where the maintenance activity must start before a given deadline and the maintenance duration increases with its starting time. They provided polynomial time algorithms to solve the problems to minimize the makespan, sum of completion times, maximum lateness, and number of tardy jobs. In the very recent, Xu et al. [11] introduced a single-machine scheduling problem with workload-dependent maintenance duration. The objective is to minimize the total completion time. For the case where the derivation of the maintenance duration function is greater than or equal to 1, a polynomial time optimal algorithm was proposed. For the case where the derivation of the maintenance duration function is less than 1, a polynomial time approximation scheme was presented. In this paper, we extend the problem proposed by Xu et al. [11]. We consider a more general objective function, i.e., the total weighted completion time. For the workload-dependent maintenance duration, we only assume that it is a nonnegative and non-decreasing function on the workload but can be computed in polynomial time. Compared to the assumption in [11], we do not require any derivation information and our assumption is more general. TheProblem statement: Given a set of non-preemptive jobs J = {J1, J2, · · · , Jn} to be processed on a single machine, where the machine is subject to a maintenance activity. All the jobs are available at time 0. For job Ji , the processing time is pi and the weight is wi , i = 1, 2, · · · , n. For the maintenance activity, its starting time is S, which is known and prefixed. However, its duration D is a nonnegative and non-decreasing function f(·) on the machine’s workload l before the maintenance activity, i.e., D = f(l), where l is the sum of processing times of jobs scheduled before the maintenance activity and function f(·) can be computed in polynomial time. Let Tf denote the time for computing function f(·). For a given schedule, let Ci denote the completion time of job Ji , i = 1, 2, · · · , n. The task is to find a schedule to minimize the total weighted completion time (P i wiCi). Adopting the well-known three-field notation scheme proposed in [2] and following the similar notations as [11], we name this problem as 1, h1, wldmt||P i wiCi , where “h1” denotes that there is a maintenance activity on the machine (a hole in the planning horizon) and “wldmt” denotes that the maintenance duration is workload-dependent. Clearly, the 1, h1, wldmt||P i wiCi problem is NP-hard, since the special case 1, h1, wldmt||P i Ci is shown as NP-hard in Xu et al. [11].