Abstract:

This paper addresses the performance of scheduling algorithms for a two-stage no-wait flowshop scheduling problem with processing flexibility and transportation, where each stage has one machine. Each job, composed of two operations, must be processed through the two stages without waiting time. We propose two approximation algorithms. The first algorithm is list scheduling and the second schedules the jobs in non-decreasing order of the total processing time of each job's two operations. We show that the worst case ratio of the algorithms is no more than 5/2 and 2, respectively. At last, we conduct numerical experiments to compare the performance of the algorithms. For the cases with different value of the parameters, we generate several instances. For every instance, the ratio of the algorithm's objective value and the optimal solution's objective value is obtained. For each case, the maximum, minimum and average value of the instances' ratio are obtained to analyze the performance of the two algorithms.

Key words: scheduling, transportation, flowshop, approximation algorithm