Non-Resumable Scheduling on a Single Bounded Parallel-Batch Machine with Flexible Maintenance

In this paper, we consider the scheduling problem on a single bounded parallel-batch machine with flexible maintenance, in which the time gap between any two consecutive maintenance is limited by a given constant and the last maintenance is required after all jobs are completed. A batch of jobs can be processed simultaneously in some available processing time interval as long as the total size of these jobs doesn’t exceed the machine capacity. The processing time of a job batch is the largest processing time of the jobs contained in this batch and the production progress is non-resumable. Our objective is to minimize the last maintenance completion time. For the case where jobs have unit processing times, we show the problem is strongly NP-hard and present a [Formula: see text]-approximation algorithm. For the case where jobs have unit sizes, we show the problem is also strongly NP-hard and provide a [Formula: see text]-approximation algorithm. Finally, we study the general case where jobs have non-identical processing times and sizes and propose a [Formula: see text]-approximation algorithm.