Integrated Scheduling of Batch Production and Intermediate Delivery with Batch-Position-Based Learning Effect

In this paper, we consider a three-stage integrated scheduling problem with learning effect motivated by the applications in semiconductor manufacturing. In the first stage, the jobs are assigned into batches to process on a batching machine, where the processing times are affected by the learning effect. In the second stage, the processed jobs are delivered by a single transporter for further processing. In the third stage, the jobs are individually processed on a single machine. Our objective is to minimize the makespan. We first propose an optimal algorithm with time complexity of O(nlog n) for the case where jobs have identical sizes. Second, for the case where jobs have identical processing time on batch machine, we propose an approximation algorithm. The absolute and asymptotic worst-case ratios are 5 3 and 11 9, respectively. Finally, for the general case where jobs have arbitrary sizes and processing times, an approximation algorithm with absolute worst-case ratio of 7 3 and asymptotic worst-case ratio of 2 is proposed.