Preemptive Scheduling of Hybrid Parallel Machines

Multioperation production facilities are often segmented into independent workcells that handle different subsets of operations. We refer to a cell that consists of several groups of uniform special purpose machines, each capable of performing only one particular operation, and one group of identical general purpose machines, that can perform all the required operations at a slower rate, as a hybrid parallel machine environment. This paper focuses on deterministic, preemptive scheduling in such an environment. We first analyze the minimum makespan for a preemptive schedule when all jobs arrive simultaneously at a hybrid machine facility. For the more general situation where jobs have arbitrary release and due dates, we adapt a network flow formulation, originally proposed for the uniform machines case, to determine whether all jobs can be completed feasibly before their respective due dates.