Anzeige
Erschienen in:
19.12.2016 | Research paper
Improved approximation algorithms for parallel machine scheduling with release dates and job rejection
Erschienen in: 4OR | Ausgabe 4/2017
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper we study a parallel machine scheduling model with different job release dates, where each job is either accepted and processed by a machine at or after its release date, or it is rejected and a certain penalty cost is paid. The objective is to minimize the makespan of the accepted job plus the total penalty of all rejected jobs. The scheduling problem is NP-hard in the strong sense. Zhang and Lu (4OR A Q J Oper Res 14:165–172, 2016) have proposed a 2-approximation for the problem, and a fully polynomial time approximation scheme (FPTAS) for the special case when the number of machines m is fixed. In this paper we present an improved 2-approximation and a polynomial time approximation scheme for the problem. We also propose an improved FPTAS for the case when m is fixed.