A New Approximation Algorithm for Two-Machine Flow Shop with Transporter Coordinate
摘要
This paper studies a two-machine flow scheduling problem with transportation time. The model assumes that there are two processing machines and single transporter with a capacity of 1. Each job is characterised by a specific physical size, and the transporter is capable of loading multiple jobs simultaneously as a batch. Each job must be processed on two processing machines in the same order and subsequently transported to the destination by the transporter. The objective is to minimize the makespan, i.e., the shortest possible time required for all jobs to be processed and transported. This paper proposes an algorithm with a guaranteed approximation ratio of \((1 + \epsilon + \frac{2}{2B^{*} - 1})\) , where \(B^*\) is the number of transportation batches that correspond to the optimal schedule and \(\epsilon \) is an arbitrary constant in (0, 1]. The approximation ratio approaches 1 as \(B^{*}\) tends towards infinity and the parameter \(\epsilon \) approaches 0. Computational experiments show that the developed approximation algorithms can efficiently generate near-optimal solutions.