Traditionally, machine scheduling research is concerned with the sequencing of tasks on one machine or on several parallel or different machines, subject to a set of constraints. Over the years, researchers have studied a huge variety of problems, developing numerous heuristics, approximation and exact algorithms, and complexity results. Some of these problems are interesting because of their intractability. Others are interesting because of their applications in production planning, personnel planning, scheduling in parallel and distributed systems, etc. For the most recent introduction to the state of the art, see Blazewicz et al. (2007).

In recent years, researchers have begun studying the scheduling problems derived from new applications and settings. For example, there are scheduling problems in decentralized systems and selfish organizations, grid computing, bioinformatics, and logistical airport operations management processes. Some of these scheduling problems reflect real-life situations by including learning effects or non-constant job processing times because of deteriorating jobs. This listing is only a small sample of the many new applications and scheduling problems that researchers are studying.

Between \(9\mathrm{th}\) and \(14\mathrm{th}\) October 2011, the \(9\mathrm{th}\) scheduling workshop entitled “New Perspectives in Scheduling Theory” was held at the Hua Jia Shan Resort and the Yuquan Campus of Zhejiang University in Hangzhou. (The participants really enjoyed the friendly atmosphere and excellent organization.) The objective of the workshop was to explore new perspectives in scheduling theory and applications that have emerged in recent years.

The papers in this special issue highlight some of the results of this workshop. We received many high-quality submissions. After the normal thorough and rigorous refereeing process that is expected of the Journal of Scheduling, only three papers were chosen for the inclusion in the special issue. The papers are listed below alphabetically by the first author.

The paper “Scheduling semi-malleable jobs to minimize mean flow time” by Hendel, Kubiak, and Trystram deals with the problem of scheduling \(\hbox {n}_\mathrm{A}\) malleable and \(\hbox {n}_\mathrm{B}\) non-malleable jobs to be executed together on two parallel identical machines to minimize mean flow time. This model is a subproblem of a more general class of multiprocessor jobs scheduling problem. The model of multiprocessor jobs has been analyzed by Blazewicz et al. (1992), while malleable jobs have been considered first in Turek et al. (1992), and a large number of papers have been devoted to scheduling malleable and multiprocessor jobs since then. In the current paper, the authors propose a set of dominant schedules for this problem and a dynamic programming algorithm that finds an optimal schedule in this dominant set in time \(\hbox {O}(\hbox {n}^{2}_\mathrm{A}\hbox {n}_\mathrm{B})\).

The paper “Scheduling parallel batch jobs in grids with evolutionary metaheuristics” by Switalski and Seredynski describes an algorithm based on recent evolutionary metaheuristic called generalized extremal optimization for scheduling jobs on computational grids. Like most of the solutions developed on computational grids, this work relies on a two-step process. The first step is to determine a suitable allocation of the jobs, followed by a greedy local algorithm. This method is compared experimentally to the classical genetic algorithm. It provides more effective solutions with a much simpler (and lower computational cost) than the genetic algorithm.

In “Two-machine interval shop scheduling with time lags,” Zhang and van de Velde consider a two-machine (flow, open, job) shop scheduling problem that involves given start and end times of jobs. More specifically, given two machines, each job has a processing time on each of the machines, a time lag, a start and an end time, and a weight. The goal is to maximize the weighted throughput. They settle the complexity of this problem and identify several special cases that can be solved by dynamic programming in polynomial time.