Maximierung der gesamten frühen Arbeit in einem verteilten Zwei-Maschinen-Fließband

Zusammenfassung Das Problem der Maximierung der gesamten frühen Arbeit in einem Zwei-Maschinen-Fließband, in dem n Aufträge unter einem gemeinsamen Fälligkeitstermin d geplant werden sollen, wurde kürzlich in der Planungs-Literatur untersucht. Zunächst wurde ein dynamisches Programmierverfahren mit einer Laufzeit von O (n² d⁴) für den gewichteten Fall vorgestellt, und dann wurde für den ungewichteten Fall ein weiteres dynamisches Programmierverfahren mit einer Laufzeit von O (n² d²) vorgeschlagen und in ein vollständig polynomiales Annäherungsverfahren (FPTAS) umgewandelt. Durch die Festlegung neuer Problem-Eigenschaften präsentieren wir einen dynamischen Programmieralgorithmus mit einer Laufzeit von O (n d²) und ein FPTAS für das ungewichtete Problem. Wir verallgemeinern das Problem auf eine verteilte Umgebung von m parallelen Zwei-Maschinen-Fließbändern, entwickeln einen dynamischen Programmieralgorithmus mit einer Laufzeit von O (n d³ m), ein FPTAS und drei Formulierungen für ganzzahlige lineare Programmierung (ILP). Computergestützte Experimente werden durchgeführt, um die vorgeschlagenen ILP-Modelle zu bewerten.