A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags |
| |
Authors: | Gwo-Ji Sheen Lu-Wen Liao |
| |
Affiliation: | Institute of Industrial Management, National Central University, No. 300, Jhongda Road, Jhongli City, Taoyuan County 32001, Taiwan, ROC |
| |
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. |
| |
Keywords: | Scheduling One machine Makespan Branch and bound algorithm Minimum and maximum time lags |
本文献已被 ScienceDirect 等数据库收录! |
|