Article ID: | iaor2002734 |
Country: | United Kingdom |
Volume: | 5 |
Issue: | 2 |
Start Page Number: | 143 |
End Page Number: | 161 |
Publication Date: | Jan 1993 |
Journal: | IMA Journal of Mathematics Applied in Business and Industry |
Authors: | Haley K.B., Lin C.K.Y. |
In many practical systems, delays in handling, transportation, and transmission, or thinking time, etc. between phases of an operation, may occur as a time lag. This study presents a scheduling problem where each job has two service phases, separated by an arbitrary time lag. The objective is to minimize the maximum completion time of all jobs in a single-server system. The job-processing order of each service phase is allowed to be different. This unary NP-hard problem is tackled by a heuristic and a modified standard approach. A study of the optimal solutions in some special cases leads to the development of greedy and iterative heuristics. An exact branch-and-bound algorithm is proposed. By deriving lower bounds from analytical results of optimal sequences, significant improvement in the efficiency is found in simulations.