On scheduling multiple two-stage flowshops (Q1985613)

Let \(J\) be a set of \(n\) jobs, where each job consists of two operations: an \(R\)-operation and a \(T\)-operation. A \textit{flowshop} is a pair of processors, one called the \(R\)-processor and the other called the \(T\)-processor. Given a set \(J\) of \(n\) jobs and a group \(M\) of \(m\) flowshops, the \textit{multiple two-stage flowshop scheduling problem} consists in assigning the jobs to the flowshops so that: -- The two operations of a job are assigned to the same flowshop. -- The \(T\)-operation of a job can start only after the \(R\)-operation has been completed. -- Operations cannot be preempted. -- The completion time of the last operation (or the \textit{makespan} of the schedule) is minimum. The flow shop scheduling problem, where each job consists of an arbitrary number of operations, is a classical problem in scheduling theory and operations research. The above multiple two-stage flowshop scheduling problem is a generalization of the classical multiprocessor scheduling problem, and therefore it is strongly NP-hard. The paper presents an efficient 2.6-approximation algorithm for the problem with running time \(O(n \log n)\). The algorithm is a simple, but clever greedy algorithm that partitions the jobs into two groups. The first group includes those jobs whose \(R\)-operation has length no more that 1.5 times the length of their \(T\)-operation; the second group contains the remaining jobs. Jobs in the first group are sorted non-increasingly by the lengths of their \(T\)-operations and they are scheduled first, greedily trying to minimize the maximum length of the \(T\)-operations in any flowshop. Then, the second group of operations are scheduled trying to greedily minimize the maximum length of the \(R\)-operations in any flowshop. The analysis of the approximation ration of the algorithm is based on a somewhat complicated case analysis.