Wieslaw Kubiak - A Book of Open Shop Scheduling: Algorithms, Complexity and Applications

More information about this series at https://link.springer.com/bookseries/6161

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

Open shop is often defined in the literature by what it is notflow shop. This definition may have originated from the initial view of open shop as a manufacturing system, where operations of a job are done in any order, without preemptions on dedicated machines. The definition fits service operations as well. A popular example of open shop is that of a library and its readers. Each reader is a job, and each book is a machine. A reader wishes to read a collection of books, and reading a book is an operation that may take different time for different readers, in any order. A book can only be read by one reader at a time, and a reader can read at most one book at a time. Another example is classteacher timetabling . Though non-preemptive open shop scheduling is a prominent part of open shop scheduling, it is preemptive open shop scheduling that makes modern open shop scheduling a universal approach to solving a broad range of real-life problems. Besides, the preemptive open shop scheduling is strongly linked to graph edge coloring and to doubly stochastic matrices, which makes it particularly attractive to study in scheduling theory.

Excellent chapters on open shop scheduling can be found in general books on scheduling by Pinedo [10], Baewicz et al. [3], Tanaev et al. [13], and Brucker [4]. Naturally, those are limited in scope. In-depth reviews are given in chapters by Gonzalez [6], Prins [11], and Woeginger [14]. Recent literature reviews of open shop scheduling have been published by Anand and Panneerselvam [2] and Ahmadian et al. [1]. However, to the authors knowledge, there has not been any monograph focusing solely on open shop scheduling published thus far. This monograph is to fill in the void, to present a growing portfolio of applications of open shop scheduling, and to emphasize a great potential and need for novel theoretical results in the open shop scheduling field.

The intended audience of the book includes, but is not limited to, sophisticated practitioners, graduate students, and researchers in operations research, management science, computer science, and discrete mathematics.

Open shop scheduling has branched out into a growing number of models by adding new features, constraints, or objective functions over the years. Therefore, a selection of topics had to be made for this book intended for fewer than 300 pages. Consequently, a balance had to be found between theory and applications, between traditional models captured by the Graham et al. [8] notation and new models that outgrew by far that notation, between graph theoretic approach to preemptive open shop scheduling and non-preemptive open shop scheduling, between existing results and open problems, and between the results that have been well-presented in the earlier books on scheduling and those that have been somewhat under-represented or more recent. As a result, the selection excludes some important open shop scheduling areas such as stochastic models, heuristics and meta-heuristics, models with machine availability, competing agents, transport delays, batch processing, and rejection, to name just few; see Ahmadian et al. [1] for a comprehensive list.

The plan of the monograph is as follows. Chapter defines notation and terminology used in this book. It also reviews the key results on edge coloring of bipartite multigraphs ( Knigs edge coloring theorem ), on fractional chromatic index (Edmonds theorem), on doubly stochastic matrices being a convex combination of permutation matrices (Birkhoffvon Neumann theorem), and the vector rearrangement theorem. Those results have proved to be the most insightful and influential for open shop scheduling. They also show an exciting diversity of perspectives that researchers have been taking at studying open shops scheduling.

Chapter deals with makespan minimization for two-machine open shop problem. The problem is one of the first open shop scheduling problems studied in the literature. Gonzalez and Sahni [7] and Pinedo and Schrage [9] give linear-time algorithms for the problem. Both algorithms have been well-presented and analyzed in books on scheduling by Pinedo [10], Baewicz et al. [3], Tanaev et al. [13], and Brucker [4] and reviews by Gonzalez [6] and Woeginger [14]. It is quite remarkable that the two-machine open shop problem with