Principles of Sequencing and Scheduling, 2nd Edition

11Stochastic Flow Shop Scheduling

11.1 Introduction

The analysis of stochastic flow shop problems has not proceeded very far and remains challenging. With few exceptions, research on the stochastic flow shop has been limited to the makespan as a performance measure, and much of the work addresses only the two‐machine problem. In the stochastic flow shop model, the makespan typically exhibits a positive Jensen gap even with two machines, so the problem is inherently more complex than its deterministic counterpart. Nevertheless, the deterministic counterpart provides an effective heuristic for large n. For small and medium numbers of jobs, we can use neighborhood search heuristics to improve upon the performance of the deterministic counterpart. With more than two machines, we can at least adapt some of the heuristic procedures developed for the deterministic counterpart, which often depend on the two‐machine solution in one way or another. Some special cases of the stochastic, two‐machine makespan problem exist – not necessarily practical ones – in which optimal sequences can be found readily. In the context of safe scheduling for the stochastic flow shop, however, we must also recognize the need for safety time.

We begin our coverage in Section 11.2 with stochastic counterparts of models covered in the previous chapter, under the assumption of stochastic independence. In Section 11.3, we introduce safe scheduling models, again subject to stochastic independence. In Section ...