An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration

An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration

0.00 Avg rating0 Votes
Article ID: iaor20123734
Volume: 23
Issue: 4
Start Page Number: 483
End Page Number: 492
Publication Date: May 2012
Journal: Journal of Combinatorial Optimization
Authors: , , ,
Keywords: combinatorial optimization
Abstract:

This paper consider m uniform (parallel) machine scheduling with linear deterioration to minimize the makespan. In an uniform machine environment, all machines have different processing speeds. Linear deterioration means that job’s actual processing time is a linear increasing function on its execution starting time. We propose a fully polynomial‐time approximation scheme (FPTAS) to show the problem is NP‐hard in the ordinary sense.

Reviews

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