Advertisement
Published in:
01-09-2020
New approximation algorithms for machine scheduling with rejection on single and parallel machine
Published in: Journal of Combinatorial Optimization | Issue 4/2020
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper we consider three machine scheduling problems with the special feature that jobs may be rejected at a certain penalty. There are n jobs which are characterized by a release date, a processing time and a penalty. Each job is either accepted and then processed by one machine, or rejected and then a rejection penalty is paid. The objective is to minimize the maximum completion time of all accepted job plus the total penalties of all rejected jobs. When jobs have identical release dates, we present a (\(\frac{3}{2}-\frac{1}{2m}\))-approximation algorithm for the parallel machine problem. When jobs have general release dates, we propose a \(\frac{4}{3}\)-approximation algorithm for the single machine problem and a (\(1+\max \{0.618,1-\frac{1}{m}\}\))-approximation algorithm for the parallel machine problem, respectively.