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

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

作　　者：胡觉亮[1] 李红芳[1] 董建明[1] 蒋义伟[1] 

机构地区：[1]浙江理工大学理学院,浙江杭州310018

出　　处：《管理工程学报》2013年第1期166-170,共5页Journal of Industrial Engineering and Engineering Management

基　　金：国家自然科学基金资助项目(11001242;11071220);浙江省自然科学基金资助项目(Y6090175;Y6090554);浙江省教育厅资助项目(Y201019076)

摘　　要：在考虑加工与运输协同调度的单机排序问题中,每个工件尺寸不同,工件在一台机器加工后,由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

关 键 词：排序 FFD算法 最坏情况界 

分 类 号：O224[理学—运筹学与控制论]