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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

4 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)143-161
Journal / PublicationIMA Journal of Management Mathematics
Issue number1
Publication statusPublished - 1993
Externally publishedYes


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.