Scheduling is essential when activities need to be allocated to scarce resources over time. Motivated by the problem of scheduling barges along container terminals in the Port of Rotterdam, this thesis designs and analyzes algorithms for various on-line and off-line scheduling problems with time lags. A time lag specifies a minimum time delay required between the execution of two consecutive operations of the same job. Time lags may be the result of transportation delays (like the time required for barges to sail from one terminal to the next), the duration of activities that do not require resources (like drying or cooling down), or intermediate processes on non-bottleneck machines between two bottleneck machines. For the on-line flow shop, job shop and open shop problems of minimizing the makespan, we analyze the competitive ratio of a class of greedy algorithms. For the off-line parallel flow shop scheduling problem with time lags of minimizing the makespan, we design algorithms with fixed worst-case performance guarantees. For two special subsets of scheduling problems with time lags, we show that Polynomial-Time Approximation Schemes (PTAS) can be constructed under certain mild conditions. For the fixed interval scheduling problem, we show that the flow shop problem is solvable in polynomial time in the case of equal time lags but that it is NP-hard in the strong sense for general time lags. The fixed interval two-machine job shop and open shop problems are shown to be solvable in polynomial time if the time lags are smaller than the processing time of any operation.

approximation algorithm, fixed interval scheduling, flow shop, job shop, on-line, open shop, scheduling, time lags, worst case analysis
Business Administration and Business Economics; Marketing; Accounting (jel M), Production Management (jel M11), Transportation Systems (jel R4)
S.L. van de Velde (Steef)
Erasmus University Rotterdam , Erasmus Research Institute of Management
Rotterdam School of Management (RSM) Erasmus University Rotterdam (EUR) Prof.dr. M.B.M. de Koster Prof.dr. A.P.M. Wagelmans Prof.dr. B. Chen
ERIM Ph.D. Series Research in Management
Erasmus Research Institute of Management

Zhang, X. (2010, July). Scheduling with Time Lags (No. EPS-2010-206-LIS). ERIM Ph.D. Series Research in Management. Erasmus Research Institute of Management. Retrieved from