工件允许转包的排序问题近似算法研究
Approximation Algorithms for Scheduling Problems with Subcontracting
陈荣军 1唐国春2
作者信息
- 1. 常州工学院理学院,江苏 常州 213032
- 2. 上海第二工业大学经济与管理学院,上海 201209
- 折叠
摘要
研究工件既可以在制造商机器上加工、又可以转包给承包商加工的排序问题,假设承包商有足够多的单机且工件在制造商及承包商机器加工均需要付出加工费用.研究制造商为自由作业、流水作业及平行机加工环境下的排序问题,目标是极小化工件最大完工时间与加工费用和.对三种排序问题,证明困难性,并设计近似算法.
Abstract
This paper studies open shop,flow shop and parallel schedulings where jobs can be either processed at manufacturer or outsourced to a subcontractor with enough single machines.Processing costs are required for both the manufacturer and the subcontractor's machines.In this paper,the in-house jobs'set and its schedule will be determined such that the sum of makespan and processing cost is minimized.For the three scheduling problems,the complexities are analyzed and approximation algorithms are proposed.
关键词
排序/近似算法/转包Key words
scheduling/approximation algorithm/subcontracting引用本文复制引用
出版年
2024
NETL
NSTL
万方数据