Scheduling with Time Lags

Scheduling means allocating limited resources to the many activities that have to be done within an organisation. Applications of scheduling theory can be found in multiple manufacturing and service industries, where production, transportation, distribution, procurement, information processing, and communication efforts are restricted by limited resources. In his dissertation <link erim events _blank>Scheduling with Time Lags, Xiandong Zhang focuses on a subset of scheduling problems which are characterised by time lag constraints, where time lags refer to the time delays between the execution of two consecutive operations of the same activity. Time lags can represent transportation delays, activities that require no limited resources, or intermediate processes between two bottleneck machines or procedures. The objective of this research was to develop efficient algorithms for solving these particular scheduling problems. Here, the word efficient means that these algorithms have relatively short running time and may result in relatively short job sequences.

Zhang’s research can be classified into two categories, the on-line algorithms and the off-line algorithms. The on-line algorithms deal with the problem that schedulers often do not have access to complete information of an instant problem and have to react to new job scheduling requests with only a partial knowledge. The off-line algorithms tackle the problem when schedulers have all relevant information of all jobs prior to scheduling.

Xiandong Zhang has defended his dissertation on July 1, 2010 at 11.30 hours. His promoter is Prof.dr. S.L. van de Velde, Professor of Management and Technology, Rotterdam School of Management, Erasmus University. Other members of the Doctoral Committee Prof.dr. M.B.M. de Koster, Prof.dr. A.P.M. Wagelmans and Prof.dr. B. Chen.

About Xiandong Zhang

Xiandong Zhang was born on January 14th, 1971 in Xuzhou, Jiangsu Province of China. He earned a Bachelor degree in Industrial Management and Engineering from Southeastern University (Nanjing, China) in 1992, and a PhD degree in Management Engineering from Tongji University (Shanghai, China) in 1997.

Xiandong Zhang has been employed at Fudan University (Shanghai, China) since 1997, as a post-doctoral researcher (1997-1999), a lecturer (1999-2000) and an associate professor (2000-).

In January 2007, Xiandong Zhang started his second PhD study at Erasmus University Rotterdam under the supervision of Professor Steef van de Velde. His research interests focus on machine scheduling and combinatorial optimization. Results from his PhD research have appeared or have been accepted for publication in the European Journal of Operational Research, Journal of Scheduling and Information Processing Letters. He was a visiting scholar at Massachusetts Institute of Technology (Cambridge, USA) (September 2001 - January 2002) and at Bocconi University (Milan, Italy) (February-June 2008).

Abstract

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.

More Information

Pictures of the Event
Full Text of the Dissertation