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 anoperation, may occur as a time lag. This study presents a schedulingproblem where each job has two service phases, separated byan arbitrary time lag. The objective is to minimize the maximumcompletion time of all jobs in a single-server system. The job-processingorder of each service phase is allowed to be different. Thisunary NP-hard problem is tackled by a heuristic and a modifiedstandard approach. A study of the optimal solutions in somespecial cases leads to the development of greedy and iterativeheuristics. An exact branch-andbound algorithm is proposed.By deriving lower bounds from analytical results of optimalsequences, significant improvement in the efficiency is foundin simulations.