Anzeige
Erschienen in:
01.08.2013
An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem
Erschienen in: Journal of Scheduling | Ausgabe 4/2013
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
Recently, Shabtay and Bensoussan (2012) developed an original exact pseudo-polynomial algorithm and an efficient \(\upvarepsilon \)-approximation algorithm (FPTAS) for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. The complexity of the FPTAS is \(O\)((\(n^{4}/\upvarepsilon \))log(\(n\)/\(\upvarepsilon \))), where \(n\) is the number of jobs. In this note we suggest another pseudo-polynomial algorithm that can be converted to a new FPTAS which improves Shabtay–Bensoussan’s complexity result and runs in \(O(n^{3}/\upvarepsilon )\) time.