平行机及自由作业的排序与转包  

Scheduling with subcontracting options under parallel and open-shop machines

作　　者：陈荣军[1] 张峰[2] 唐国春[2] 

机构地区：[1]常州工学院数学系,江苏常州213002 [2]上海第二工业大学管理工程研究所,上海201209

出　　处：《系统工程学报》2011年第5期649-655,共7页Journal of Systems Engineering

基　　金：国家自然科学基金资助项目(70731160015);江苏省自然科学基金资助项目(yw06037)

摘　　要：研究工件排序与转包相联的模型,即制造商从客户处接受一批工件,这些工件既可以由制造商加工,也可以一定费用转包给承包商加工.制造商需要确定被转包的工件集及工件的加工顺序,使得加工费用和转包费用之和为最小.研究制造商为平行机及自由作业,承包商为单机情况下的排序与转包模型,基于动态规划算法给出了近似算法,并分析了该算法的性能比.This paper studies models on scheduling with subcontracting options under parallel and open-shop machines. In the models a manufacturer receives a set of jobs from its customers at the beginning of the planning horizon. Each job can be either processed by manufacturer＇s machines in-house or subcontracted to subcontractor＇s machines at costs. The manufacturer needs to determine which orders should be produced in-house and which orders should be subcontracted. Furthermore, it needs to determine a production sched- ule for all orders. The objective is to minimize the sum of production and subcontracting cost. Based on the dynamic programming algorithm, a approximate algorithm with worst-case performance analysis is given for the problems under manufacturer＇s parallel and open shop machines and subcontractor＇s single machine respectively.

关 键 词：排序 转包 近似算法 平行机 自由作业 

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