Principles of Sequencing and Scheduling, 2nd Edition

9Parallel‐machine Models

9.1 Introduction

In general, scheduling requires both sequencing and resource allocation decisions. When there is only one resource, the allocation of that resource is completely determined by sequencing decisions. As a consequence, in the single‐machine model, no distinction exists between sequencing and resource allocation. To appreciate that distinction we must examine models with more than one machine. Scheduling theory covers three basic types of multimachine models: parallel systems, serial (flow shop) systems, and hybrid (job shop) systems. In parallel systems, jobs consist of one operation, as in the single‐machine model; but in flow shops and job shops, the structure of jobs is more complicated. This chapter treats the case of parallel machines, whereas the following chapters introduce the other multimachine models.

A simple setting in which we can investigate the effects of parallelism is the problem of scheduling single‐operation jobs in the presence of several parallel machines. As in the basic model, n jobs are simultaneously available at time zero. We also have m parallel machines available for processing, and we assume that a job can be processed by at most one machine at a time. In the basic parallel‐machine model, the machines are identical and the jobs are unrelated. When we address the fundamental performance measures in this setting, solutions reflect resource parallelism.

9.2 Minimizing the Makespan

In the basic single‐machine ...