费用有限的柔性两机自由作业与流水作业排序问题  

Flexible Open Shop and Flow Shop Schedulings with Two Machines and Limited Cost

作　　者：陈荣军[1] 唐国春[2] CHEN Rong-jun;TANG Guo-chun(School of Sciences,Changzhou Institute of Technology,Changzhou 213032,China;Institute of Management Engineering,Shanghai Second Polytechnic University,Shanghai 201209,China)

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

出　　处：《数学的实践与认识》2022年第4期12-18,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(71371120)。

摘　　要：研究制造商加工环境为两机自由作业和流水作业柔性排序问题,即工件既可以在制造商两台机器上加工,又可以转包给承包商机器加工.承包商有足够多机器,使得每台机器至多加工一个工件.工件在制造商及承包商机器上所需加工时间及费用均不同.本文需要确定被转包的工件集及未转包工件的加工顺序,在加工及转包总费用不超过给定值的情况下,分别极小化工件最大完工时间及工件总完工时间.证明了四个问题的NP困难性,并对自由作业情形设计多项式时间近似算法.This paper studies flexible open shop and flow shop schedulings with two machines,in which jobs can be either processed at a manufacturer ’s machines or subcontracted to a subcontractor.The subcontractor has enough machines such that at most one job is processed at each machine.The processing time and cost of each operation at manafacturer ’s and subcontractor’s machine are different.In this paper,the jobs’ set subcontracted and the in-house schedule will be determined such that,whithin the total cost of subcontracting and processing,the makespan and total completion time are minimized,respectively.The complexities of four problems are analyzed and two polynomial approximation algorithms for open shop problems are proposed.

关 键 词：排序 转包 近似算法 自由作业 流水作业 

分 类 号：TH165[机械工程—机械制造及自动化] O223[理学—运筹学与控制论]