Parallel Machine Scheduling on Jobs and Partial Maintenance Activities due to job-Dependent Machine Deteriorations

摘要

In this article, we consider a parallel machine scheduling problem that integrates partial maintenance activities due to job-dependent machine deteriorations. In this problem, we are given identical parallel machines, each with an initial maintenance level which is a non-negative integer value to represent its maintenance state, and a set of jobs each with a non-preemptive processing time and a machine deterioration. For each job, its machine deterioration qualifies the decrement of the machine maintenance level after processing it. When each machine processes jobs, one should guarantee a non-negative maintenance level at any time point. Thus, whenever necessary, a maintenance activity must be performed to restore the machine maintenance level. The goal of this problem is to schedule the jobs and the maintenance activities, such that the makespan achieves the minimum. We take the partial maintenance activity pattern, in which each activity can be performed to increase the machine maintenance level to any level not exceeding the maximum. To tackle this problem, we first model it by an integer programming formulation, and then propose an LP-based approximation algorithm with an instance-dependent approximation factor and show the approximability lower bound. Finally, we present a fast heuristic algorithm followed by a numerical example to show how this algorithm works.