CAJ | 학술논문

在考虑加工与运输协同调度的单机排序问题中,每个工件尺寸不同,工件在一台机器加工后,由m辆有容量限制的运输工具运送到同一个顾客处,目标是极小化最后一个送到其顾客的工件的到达时间,本文给出了该问题的一个最优算法,并且证明了该算法的最坏情况界为3/2。
재고필가공여운수협동조도적단궤배서문제중,매개공건척촌불동,공건재일태궤기가공후,유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.