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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A New Approximation Algorithm for Two-Machine Flow Shop with Transporter Coordinate

  • Yinling Wang,
  • Yuping Ge,
  • Yubai Zhang,
  • Hui Tian

摘要

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.