Skip to main content

Über dieses Buch

Although several monographs and edited volumes have discussed scheduling in general, most of these works survey the field by contributing a single chapter to production systems like flow shops. Flow Shop Scheduling: Theoretical Results, Algorithms, and Applications is solely dedicated to bringing together a huge body of knowledge on the subject, along distinct design features, in order to help scholars and practitioners easily identify problems of interest. This monograph has been organized into ten distinct flow shop systems and explores their connections. The chapters cover flow shop systems including two-machine, flexible, stochastic, and more. Outside of the traditional flow shops that require a job never revisits any stage, this book also examines the reentrant flow shop, in which a job may cycle back and be reprocessed at the same station or sequence of stations, multiple times.

The authors have made the material accessible to a broad readership, using simplified notation and revealing unifying concepts. The results unique to flow shop research should provide the seed for research in other areas of scheduling and in optimization in general.



Chapter 1. Introduction

We start by presenting the basic structure and language of flow shops, and the conventions and notation to be adopted. The concepts of precedence, permutation schedules and when they are optimal, graphic schedule representations, dominance properties, heuristics and error bounds, cyclic shops and other fundamentals are introduced.

Hamilton Emmons, George Vairaktarakis

Chapter 2. The Two-Machine Flow Shop

The two-machine flow shop has attracted significant attention, especially when it comes to extensions of the basic makespan model to include release times, setups, or other complications. As expected, we start our coverage with a full discussion of Johnson’s Rule for makespan minimization. Then, we present extensions that incorporate setup/teardown times in automated manufacturing cells. When arbitrary positive release times are assumed for jobs, the problem of minimizing makespan in the two-machine flow shop is shown to be NPcomplete, and hence we discuss solution procedures, optimal and heuristic. Even when a single server is used to perform setups, the problem is shown strongly NP-complete, though special cases accept simple solutions. Results on optimal lot streaming of a product are also presented. Precedence constraints are postponed to a later chapter. Subsequently, we survey results on objectives like Σ

Cj, L



max, Σ


, Σ


, as well as corresponding multicriteria. Various manifestations of these models come with setups, scarce resources, common deadlines, etc. Whenever possible, we provide dominance properties, lower bounds, branch-andbound approaches, heuristics and computational results.

Hamilton Emmons, George Vairaktarakis

Chapter 3. Transfer Lags in the Flow Shop

We define the types of transfer lags, positive and negative, between stages of a flow shop, and discuss applications (transport times, nonbottleneck machines, manufacturing cells, batch transfers, setup and teardown times, master-slave systems, etc.). We show that the twomachine makespan problem is NP-hard, but that a variety of models can be efficiently solved using the Modified Johnson’s Rule and its extensions when our search is restricted to permutation schedules. We extend the analysis to the two-stage hybrid shop, and then to the


machine shop, for which bounds and heuristics are given. Further results involving transfer lags are given in Chap. 4.

Hamilton Emmons, George Vairaktarakis

Chapter 4. The m-Machine Flow Shop

Considered to be a very general case of flow shop systems, the


-machine flow shop is the most researched system in all of flow shop theory. Beyond solving the problem under a variety of objectives and side constraints, the


-machine flow shop serves as a test bed for new methodological tools. Regarding solutions, the research presented in this chapter is rich in lower bounding schemes, dominance properties, heuristic algorithms and computational experiments measuring their success. The models considered not only deal with all the standard regular performance measures, but also application-specific objective functions. A lot of work is also available on problems with multiple objectives. We find that the most successful solutions on problems of practical size are due to metaheuristic implementations including simulated annealing, tabu search and genetic algorithms. In contrast, branch-and-bound algorithms are mostly inadequate.

Hamilton Emmons, George Vairaktarakis

Chapter 5. The Hybrid Flow Shop

In this chapter we organize the literature on the hybrid flow shop scheduling problem that has appeared since the late 1950’s. We see a number of interesting and diverse industrial applications of this system, and find that the majority of research focuses on the makespan objective. Our coverage of results is exhaustive and categorized along concepts such as complexity, error-bound analyses, computational experiments and choice of objective. Several new results are included that have not appeared in the literature before. Surprisingly, existing research does not focus on the deterministic version of the problem alone, but also on the case of stochastic processing times.

Hamilton Emmons, George Vairaktarakis

Chapter 6. The No-Wait Flow Shop

After describing some real-world examples of flow shops with no waiting, we demonstrate the equivalence of no-wait and blocking in the shop with


= 2. For the no-wait shop, some research is available on the flow time objective while the majority of research focuses on the makespan objective. Hence, we start with a detailed discussion of an






) algorithm for





. For the makespan objective and


> 2 machines, we present a plethora of polynomially solvable special cases of the problem. Most interesting is the case with semi-ordered processing time matrices. In this case, a so called

pyramidal schedule

provides an optimal solution in





) time. Heuristic algorithms for


> 2 and the makespan objective show that the problem is intimately related to the traveling salesman problem. We survey the state of the art on metaheuristics. The problem is analyzed in the presence of lot streaming, with separable setup and teardown times, and in assemblytype and hybrid flow shops.

Hamilton Emmons, George Vairaktarakis

Chapter 7. Blocking or Limited Buffers in Flow Shops

We begin by reviewing many manufacturing and other applications of the flow shop with limited or no interstage storage. For two machines, we show the equivalence of no storage (blocking) and no waiting, which have a polynomial solution; for


> 2, we establish that the flow shop with blocking is NP-complete. An integer program is given to find the minimum makespan. A variety of bounds are presented. Branch-and-bound algorithms using these bounds are given and evaluated. Various heuristics and metaheuristics are presented and compared. Two different precedence graphs are introduced and used in the above developments. The total tardiness objective is also discussed.

Hamilton Emmons, George Vairaktarakis

Chapter 8. Flexible Flow Shops

We introduce four types of flexibility encountered in a flow shop: job routing through a hybrid shop, machine assignment, allocation of a scarce resource over the tasks to speed up processing, and the composition of daily production batches to satisfy requirements for a finite set of parts over a finite horizon. Two forms of machine flexibility are considered: multitasking where a machine can do more than one task of a job, and multiprocessing where several machines may combine to process a task. In each case, we present some or all of the following: complexity results, solution algorithms or heuristics with worst case performance, and assessments on the benefits of flexibility.

Hamilton Emmons, George Vairaktarakis

Chapter 9. Reentrant Flow Shops

We introduce flow shops that revisit certain processors, and define the common patterns of flow: cyclic, chain, hub, and V-shaped. We show that even the simplest case, the (1,2,1)-reentrant shop, is NPhard, establish properties that facilitate a branch-and-bound algorithm, and present two simple but very effective heuristics. With m machines, we give for chain-reentrance simplifying properties, for hub-reentrance a DP based on simplifying assumptions that yet performs well, for Vreentrance a solvable special case. For cyclic production of a single product in the general m-machine reentrant shop, we give an algorithm for finding the efficient frontier between cycle time and flow time, and a heuristic for larger instances. For the hybrid reentrant system, if all jobs require the same time for each production step but have different due dates, dispatching rules are recommended and compared.

Hamilton Emmons, George Vairaktarakis

Chapter 10. The Robust Flow Shop

In this chapter, job processing requirements are considered to be uncertain. They are no longer assumed to be deterministically known. One modeling approach would be to consider processing time probability distributions, and indeed this is done in a later chapter. Here, we provide a standard minimax regret approach, which however has been exploited very little in the context of scheduling. The limited research that has been conducted on this topic demonstrates that the minimax regret approach is particularly useful in scheduling problems because the corresponding solutions are quite robust on processing time variations. On a negative note, the available research indicates that this technique is at least a level of magnitude harder to deal with than its deterministic counterpart.

Hamilton Emmons, George Vairaktarakis

Chapter 11. Stochastic Flow Shops

When job parameters are uncertain or unpredictable, new types of policies become possible. Besides static policies, we now should consider dynamic policies, with or without preemption. Objectives too have more variety. The makespan, for example, is now random; we usually choose to minimize its expectation.

We present new conditions under which permutation schedule are optimal for two or three machines. If these do not hold, then to minimize expected makespan on two machines:

A simple optimum exists when task times are exponential;

for arbitrary distributions, Johnson’s Rule is asymptotically optimal;

three simple heuristics have been tested using log normal distributions, and give good results in combination.

For more than two machines, we report the very limited results that have been published.

Hamilton Emmons, George Vairaktarakis


Weitere Informationen

Premium Partner

Stellmach & BröckersBBL | Bernsau BrockdorffMaturus Finance GmbHPlutahww hermann wienberg wilhelm

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.



Künstliche Intelligenz und der Faktor Arbeit - Implikationen für Unternehmen und Wirtschaftspolitik

Künstliche Intelligenz und ihre Auswirkung auf den Faktor Arbeit ist zum Modethema in der wirtschaftswissenschaftlichen Politikberatung avanciert. Studien, die alarmistisch die baldige Verdrängung eines Großteils konventioneller Jobprofile beschwören, leiden jedoch unter fragwürdiger Datenqualität und Methodik. Die Unternehmensperspektive zeigt, dass der Wandel der Arbeitswelt durch künstliche Intelligenz weitaus langsamer und weniger disruptiv ablaufen wird. Jetzt gratis downloaden!