Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
483018 | European Journal of Operational Research | 2007 | 15 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Gwo-Ji Sheen, Lu-Wen Liao,