考虑加工与运输协同调度的单机排序问题

Coordinating Production and Transportation of Jobs to Solve Single Machine Scheduling Problems

在考虑加工与运输协同调度的单机排序问题中,每个工件尺寸不同,工件在一台机器加工后,由m辆有容量限制的运输工具运送到同一个顾客处,目标是极小化最后一个送到其顾客的工件的到达时间,本文给出了该问题的一个最优算法,并且证明了该算法的最坏情况界为3/2。

Supply chain management has been one of the most important and widely discussed topics in the production and operation field over the last decade. Generally speaking, a supply chain includes all the interactions among suppliers, manufactures, distributors, and customers. Due to market globalization, coordination among different stages in the supply chain to optimize overall system performance has become more practical and received attention from both industry professionals and academic researchers. In particular, the linkage between job scheduling and delivery of finished jobs is extremely important. Job scheduling and delivery of finished jobs are two critical steps in supply chain management, and they play important roles in the supply chain. The coordination between job scheduling and delivery of finished goods can improve customer service level, reduces operational cost, and optimize the whole system. In this paper, we consider a two-stage supply chain scheduling problem in which the first stage is job scheduling and the second stage is job delivery. Jobs are delivered in batches by a vehicle. The key problem is to coordinate scheduling and transportation of jobs with the objective of minimizing the time taken to have the last finished job arrive at its customer. In the study of the supply chain scheduling problem, many researches have considered scheduling problems with only one vehicle or unlimited vehicles. In this paper, we consider the more general case of the problem in which limited vehicles are employed and each job may occupy a different amount of physical space in a vehicle. The problem is described formally as follows： jobs are first processed by a single machine, and then delivered by mcapacitated vehicles to a single customer. The machine can handle at most one job at any time. Jobs require varying physical space while being loaded into a vehicle. The preemption of its processing is not allowed. The goal is to minimize the time before the last finished job arrives at its customer. Four steps are needed to determine a schedule for the problem： the composition of batches, the sequencing of jobs within a batch, the sequencing of batches to be processed on the machines and the transportation strategy for the completed batches. The main idea for the optimal approximation algorithm provided in this paper is described as follows： Assign jobs into batches using FFD algorithm, followed by sequencing batches in the non-decreasing order based on the sum of processing times for jobs in each batch. Jobs within each batch can be sequenced in an arbitrary order. Assign each batch to the vehicle by a given rule. Dispatch each completed but undelivered batch whenever a vehicle becomes available.