Scheduling two-phase jobs with arbitrary time lags in a single-server system

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-andbound algorithm is proposed. By deriving lower bounds from analytical results of optimal sequences, significant improvement in the efficiency is found in simulations. © 1993 Oxford University Press.