Program description
The research program covers a broad spectrum of topics in the areas of Statistics and Operations Research. Most of the research in the program is methodologically-oriented, but has natural applications in production processes, process design and development, logistics, transportation, scheduling and planning, computer technology, and communications. In line with this, members of the program maintain extensive contacts with both academia and industry. Knowledge transfer is also given a lot of attention: the program members have organized a large number of workshops and conferences, and taught courses in several graduate networks.
Key research topics presently are:
Research activities cover the complexity analysis of optimization and approximation problems, including the derivation of performance guarantees, decision-making with incomplete information, the development of optimization algorithms, with an emphasis on the investigation of integer linear programming models, and the design of heuristic search methods.
Methodologically speaking, we put an emphasis on:
Program management
Prof.dr. R.J. Boucherie, prof.dr.ir. O.J. Boxma
Senior researchers involved
Dr.ir. I.J.B.F. Adan, prof.dr. J.L. van den Berg, prof.dr.ir. S.C. Borst, prof.dr. R.W. van der Hofstad, dr. J.L. Hurink, dr.ir. C.A.J. Hurkens, dr. J.S.H. van Leeuwaarden, prof.dr. J.K. Lenstra, dr. N. Litvak, dr. J.C.W. van Ommeren, dr. J.A.C. Resing, dr.ir. W.R.W. Scheinhardt, dr. R.A. Sitters, dr. L. Stougie, dr. J.D. Vink-Timmer, prof.dr.ir. J. van der Wal, prof.dr. G.J. Woeginger, prof.dr. W.H.M. Zijm.
Research highlights
Complexity of planning problems: For many well-studied combinatorial optimization problems no efficient exact algorithm is known. Theoretical computer science has developed the theory of NP-hardness, which gives a partial explanation for these phenomena. As a main focus of our research over the review period, we have investigated a number of combinatorial optimization problems, derived NP-hardness results for them, and also studied their approximability from the worst case point of view. Rene Sitters’ PhD research has been trend-setting and generated a host of results on routing and scheduling problems. In particular, Sitters established (i) the NP-hardness of the traveling repairman problem on line metric spaces under release dates, and (ii) the NP-hardness of the preemptive sum of completion time scheduling problem on unrelated parallel machines. Problem (i) had been open since the mid-1970s, and problem (ii) had been open since 1992.
Resource allocation: In a joint project of Philips Research and EURANDOM, Johan van Leeuwaarden has modeled multi-access protocols in cable access networks via queuing models involving multi-dimensional Markov chains. His elegant analytic and asymptotic techniques yield much insight into these multi-access protocols. He earned the Beta-prize for the best PhD thesis in 2004-2005 within Beta and the 2008 Doctoral Dissertation Award for Operations Research in Telecommunications of INFORMS.
In a joint PhD project with TNO ICT, Ericsson, Twente Institute for Wireless and Mobile Communications and TU Delft, Sing Kong Cheung obtained approximations and boundaries for sojourn times in (Discriminatory) Processor Sharing queues, and applied these results to investigate prioritization rules in IEEE 802.1x wireless systems.
Another form of resource allocation occurs in polling models: models of several queues which are attended by a single server, usually in cyclic order. In a joint PhD project at the TU/e departments of Technology Management and Mathematics & Computer Science, Erik Winands has studied polling models for Stochastic Economic Lot Scheduling. This has led to important theoretical and practical results, such as an MVA scheme for polling systems.
Key publications
National and international cooperation
All groups in this program maintain extensive international contacts. Partly this is formalized via participation in or coordination of an international research program or the coordination of research projects in EURANDOM, the European research institute in Statistics, Probability and Stochastic Operations Research that is located in Eindhoven.
The combinatorial optimization group participated in the BRICKS project IS3 on 'Decision Support Systems for Logistic Networks and Supply Chain Optimization', and in the European ARRIVAL project on railway optimization ('Algorithms for Robust and online Railway optimization: Improving the Validity and reliAbility of Large scale systems'). The combinatorial optimization group is involved in joint projects with Università di Roma ‘La Sapienza’, the Charles University of Prague, the Katholieke Universiteit Leuven, the University of Warwick, the University of Durham, Pittsburgh University, the University of Bergen, etc.
There is an intensive collaboration in queuing theory and performance analysis between groups at CWI and Beta groups in Twente and Eindhoven. Presently they are collaborating in the BSIK BRICKS project, an NWO project, and the QPA project of EURANDOM (among others). Their collaboration is also formalized in E-Quality, which also involves groups in TNO ICT and TU Delft. The Twente and Eindhoven groups are also jointly responsible for a collection of queuing courses in LNMB, the Dutch Graduate network in the mathematics of operations research, and they have jointly organized several workshops. Internationally, there is participation in a few European NoE (Networks of Excellence) and some other European programs. Among the various international contacts we'd also like to mention the fruitful collaboration with Carnegie-Mellon University, with various long-term visits from both sides, and two workshops and the collaboration with INRIA.
Application of research and collaboration with industry
While most of the research in this program is of a fundamental nature, it is almost invariably inspired by real-life problems. Master theses are typically completed during a traineeship at a company. During the review period, there have been joint projects with Philips Research, Vodafone and Vanderlande Industries, TNO ICT, Thales, as well as some STW projects.
Outlook 2009-2014
Research in combinatorial optimization in Eindhoven will be oriented toward planning problems in railway optimization and telecommunication. Railway optimization will be studied within the European ARRIVAL project, and telecommunication problems will be studied within a project with the French TeleCom. Emphasis will also be placed on time-tabling problems (for instance for sports competitions) and on the analysis of on-line algorithms. The expertise in enumerative optimization, implementation and practical problem-solving will be maintained. In Twente, there will be a focus on scheduling of adjacent resources such as in berth allocation of ships, scheduling of parallel processors in a computer system and flight assignment to check-in desks at airports. The first results have been obtained for both theoretical and practical scheduling problems, but many challenges lie ahead.
Research in performance analysis will methodologically concentrate on analytic and asymptotic methods. Regarding applications, there is a growing interest in logistics issues in healthcare, in the performance analysis of self-organizing and ad-hoc networks, and in analysis, optimization and control of polling systems.
Collaboration within Beta will be strengthened via LOIS in Eindhoven, and the CTIT SRO Industrial Engineering & ICT in Twente. Furthermore, the Eindhoven and Twente groups participate in NIRICT.