Anzeige
Erschienen in:
01.05.2023
Algorithms for single machine scheduling problem with release dates and submodular penalties
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2023
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 consider the single machine scheduling problem with release dates and submodular penalties, in which each job can be either assigned to the machine or rejected. The objective is to minimize the sum of the makespan of the processed jobs and the penalty of the rejected jobs which is determined by a submodular function. First, we present a simple algorithm for the off-line problem. Second, for the on-line problem, we prove that there is no on-line algorithm with a constant competitive ratio if the penalty submodular function is not monotone, and present an on-line algorithm with a competitive ratio of 3 if the penalty submodular function is monotone. Finally, we consider a special case of the on-line problem in which all jobs have the same release date. We prove that there is no on-line algorithm with a competitive ratio of \(\frac{\sqrt{5}+1}{2}\approx 1.618\), and the competitive ratio of the on-line algorithm we presented is 2.