Anzeige
Erschienen in:
05.06.2020
A tight approximation algorithm for problem \(P2\rightarrow D|v=1,c=1|C_{\max }\)
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2022
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
This paper focuses on the scheduling problem on two parallel machines with delivery coordination. In particular, given a set of n jobs, we aim to find a schedule with a minimal makespan such that all jobs are first executed on two parallel machines then delivered at the destination with a transporter. This problem is known to be NP-hard Chang and Lee (Eur J Oper Res 158(2):470–487, 2004), cannot be solved with an approximation ratio strictly less than 3/2 unless P=NP. We close the gap by proposing a polynomial time algorithm whose approximation ratio is \(3/2+\varepsilon \) with \(\varepsilon >0\), improve the previous best ratio \(14/9 + \epsilon \).