Approximation schemes for single-machine scheduling with a fixed maintenance activity to minimize the total amount of late work

Approximation schemes for single-machine scheduling with a fixed maintenance activity to minimize the total amount of late work

0.00 Avg rating0 Votes
Article ID: iaor20162104
Volume: 63
Issue: 2
Start Page Number: 172
End Page Number: 183
Publication Date: Mar 2016
Journal: Naval Research Logistics (NRL)
Authors: , , , ,
Keywords: manufacturing industries, scheduling, combinatorial optimization, maintenance, repair & replacement, programming: dynamic, heuristics
Abstract:

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.

Reviews

Required fields are marked *. Your email address will not be published.