The 2019 workshop on models and algorithms for planning and scheduling problems was held in Renesse (The Netherlands). Following the workshop, we invited a few of the papers for publication in a special issue of journal of scheduling. After several rounds of reviews, three of the papers were finally selected for publication.

The paper "The flexibility of home away pattern sets" by Lambers, Goossens and Spieksma addresses a very interesting dilemma of trying to come up with a schedule for a sports league for 2n teams, where in each round teams play Away and Home games. A round is nothing but a matching, and the plan is that in the 2n-1 days, every team plays every other time. Abstractly it is a partitioning of the clique into matchings. What makes it more complex is that games are either “Away” games or “Home” games and the ideal schedule more or less alternates between these two. This is not always possible and so a team might have consecutive away games or consecutive home games. The paper is about the mathematics of feasible home–away pattern sets and to characterize the different types of feasible patterns and to measure their quality.

The paper “Malleable scheduling beyond identical machines” by Fotakis, Matuschke and Papadigenopoulos made a very important contribution on enhancing our theoretical understanding of the space when a job can be parallelized and the run time drastically reduced by allocating it to a larger number of machines. They present both very interesting and non-trivial upper and lower bounds for this problem. Their algorithms do better on models where the machines have identical speeds for example. All the results are based on LP rounding.

The paper “Well-behaved Online Load Balancing Against Strategic Jobs” by Li, Li and Wu considers a truthful online load-balancing problem with the objective of the makespan minimization on related machines. In this setting, it is important to have a schedule that is well-behaved that is where the load on high-speed machines is higher. However, the existing truthful online load-balancing algorithms so far were not well-behaved. This paper gives several results with both lower and upper bounds and shows how to design schedules that are almost well-behaved with a good competitive ratio.

We thank all the reviewers for their hard work and detailed comments. We are grateful to Edmund Burke for their patience in working with us.

Guest Editors

Samir Khuller (Northwestern University)

Amit Kumar (IIT Delhi)

Shi Li (University of Buffalo)

Ben Moseley (Carnegie Mellon University)

Barna Saha (University of California San Diego)