A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags

Gwo Ji Sheen, Lu Wen Liao

研究成果: 雜誌貢獻期刊論文同行評審

5 引文 斯高帕斯(Scopus)

摘要

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time.

原文???core.languages.en_GB???
頁(從 - 到)102-116
頁數15
期刊European Journal of Operational Research
181
發行號1
DOIs
出版狀態已出版 - 16 8月 2007

指紋

深入研究「A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags」主題。共同形成了獨特的指紋。

引用此