Summary of Research Results
One of the fundamental results of the project is a comprehensive 150-page survey article (Chen, Potts & Woeginger, 1998) published in the Handbook of Combinatorial Optimization. In this article, we described and explained the existing analytical as well as empirical approaches to solving sequencing and scheduling problems. This article has been cited by an increasing number of researchers in their work on algorithmic aspects of sequencing and scheduling. Chen (1999) surveys research on efficient on-line scheduling algorithms and their competitiveness with off-line algorithms, where on-line algorithms differ fundamentally from off-line ones: In on-line problems, partial solutions are required before all problem data are available and these data are made gradually available over time. Decisions based on partial solutions are irrevocable due to the passage of time. In another article (Chen, 2000a) published in the Encyclopaedia of Mathematics, both experience-based approach and sciencebased approach have been described and commented. One of the algorithms strikes an excellent balance between efficiency and effectiveness and has been used as a touchstone for more involved approaches. At a more basic level, several smaller articles (Chen, 2000b) to be published in The Informed Student Guide to the Management Sciences provide beginners in management sciences with basic knowledge of quantitative methods and analysis. All of the aforementioned articles have served as a knowledge base for the project. All scheduling problems this project studied are inherently intractable, i.e., it is extremely unlikely that these problems can be solved to optimality in their general form in practice. An efficient algorithm is given in (Du, Han & Chen, 1997) for solving a scheduling problem with general precedence constraints, in which an activity must start and finish within a time window after its predecessor activity has already finished. Problems like this can arise from scheduling athletic competitions such as the Olympic Games. The algorithm is guaranteed to deliver a solution that may deviate from the best possible by at most a third. Scheduling problems where at least two resources must be allocated to activities over time have been studied under various environments. These environments include on-line decision making and activities requiring different set-up periods or may be pre-empted, i.e., an activity is allowed to be stopped and resumed at a later time to allow the resources allocated to it to be re-allocated to some more profitable activity. Efficient algorithms incorporating empirical experience are provided with high quality performance guarantees (Chen, Vestjens & Woeginger, 1997; Chen, Potts & Strusevich, 1998; Chen & Yu, 2001; Chen, Du, Han & Wen, 2001; Zhang, Wang, Chen & Zhang, 2000). Models of allocation of bandwidth and storage are considered in (Chen, Hassin & Tzur, 2000), in which one faces a number of independent requests, respectively, for reservation of bandwidth of a communication channel of fixed capacity and for storage of items into a space of fixed size. In both problems, a request is characterised by (a) its required period of allocation, (b) its required bandwidth (item width, respectively) and (c) the profit of accepting the request. The problem is to decide which requests to accept so as to maximise the total profit. Efficient and effective algorithms are provided for solving various special cases. A focal task of this project was to solve scheduling problems in air-traffic control with a 1

united approach of both theoretical and empirical analyses. After working with the European Organisation for the Safety of Air Navigation (EUROCONTROL), my collaborators and I proposed different solution approaches and test them on real traffic data. We also discussed the usability of these approaches under various circumstances. Some results are summarised in (Leal de Matos, Chen & Ormerod, 2000) and some other results have been presented to EUROCONTROL during my one-week visit to them. Our approaches similar to those used for air-traffic control were applied to problems in manufacturing and telecommunications and reported in (Chen, Deng & Zang, 2000). With their own characteristics, these problems involved higher degree of complexity in topology. Theories and techniques in network optimisation were incorporated into our study.

References:
Chen, B., 1999. A review of on-line machine scheduling: algorithms and competitiveness. Mathematical Theory and Applications, vol. 19, 1–15. Chen, B., 2000a. “LPT sequencing” and “UET scheduling”, Encyclopaedia of Mathematics, Supplement II (M. Hazewinkel, Ed.), Kluwer Academic Publishers. Chen, B., 2000b. Eleven entries in The Informed Student Guide to the Management Sciences (R.L. Flood, and H.G. Daellenbach, eds.), International Thomson Publishing. To appear. Chen, B., X. Deng and W. Zang, 2000. On-line scheduling a batch processing system to minimize total weighted job completion time. Submitted for journal publication. Chen, B., D. Du, J. Han and J. Wen, 2001. On-line scheduling of small open shops, Discrete Applied Mathematics 110 (2–3) (2001). 133–150. Chen, B., R. Hassin and M. Tzur, 2000. Allocation of bandwidth and storage, to appear in IIE Transactions on Scheduling and Logistics. Chen, B., C.N. Potts and V.A. Strusevich, 1998. Approximations for two-machine flow shop scheduling with batch set-up times. Mathematical Programming, vol. 82, 255–271. Chen, B., C.N. Potts and G.J. Woeginger, 1998. A review of machine scheduling: complexity, algorithms and approximability. Handbook of Combinatorial Optimization (Volume 3) (Editors: D.-Z. Du and P. Pardalos), Kluwer Academic Publishers. 21–169. Chen, B., A.P. Vestjens and G.J. Woeginger, 1997. On-line scheduling of two-machine open shops where jobs arrive over time, Journal of Combinatorial Optimization, vol. 1, 355– 365. Chen, B., and W. Yu, 2001. How good is a dense shop schedule? Acta Mathematicae Applicatae Sinica 17 (1) (2001). 121–128. Du, D., J. Han and B. Chen, 1997. An improved heuristic for one-machine scheduling with delays constraints. Sciences in China, vol. 40, 680–686. Leal de Matos, P., B. Chen and R. Ormerod, 2000. Optimisation models for re-routing airtraffic flows in Europe. To appear in Journal of the Operational Research Society. Zhang, Y., S. Wang, B. Chen and S. Zhang, 2000. On-line preemptive scheduling on related machines. Submitted for journal publication.

2