Flow Shop Scheduling

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.

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, Lmax, Tmax, ΣTj, ΣUj, 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.

Considered to be a very general case of flow shop systems, the m-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 m-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.

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.

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 m = 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 O(n log n) algorithm for F2|nwt|C _max. For the makespan objective and m > 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 O(n ²) time. Heuristic algorithms for m > 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.

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.

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.

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.

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:

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