Scheduling batches with sequential job processing for two-machine flow andopen shops

In this paper, we study a problem of scheduling and batching on two machine s in a flow-shop and open-shop environment. Each machine processes operatio ns in batches, and the processing time of a batch is the sum of the process ing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is process ed. The aim is to make batching and sequencing decisions, which specify a p artition of the jobs into batches on each machine, and a processing order o f the batches on each machine, respectively, so that the makespan is minimi zed. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines ; we refer to these as consistent batches. A heuristic is developed that se lects the best schedule among several with one, two, or three consistent ba tches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By pr oving the existence of an optimal solution with one, two or three consisten t batches, a close relationship is established with the problem of scheduli ng two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to he derived, and various heuristic m ethods to be suggested.