带模具约束的两台同型机排序问题的改进算法  

An improved algorithm for two identical machines scheduling with mold constraints

作　　者：甄谭 张安[1] 陈光亭[2] 陈永[1] ZHEN Tan;ZHANG An;CHEN Guangting;CHEN Yong(School of Sciences,Hangzhou Dianzi University,Hangzhou Zhejiang,310018,China;School of Electronics and Information Engineering,Taizhou University,Taizhou Zhejiang,318000,China)

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018 [2]台州学院电子与信息工程学院,浙江台州318000

出　　处：《杭州电子科技大学学报（自然科学版）》2022年第2期86-89,共4页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：国家自然科学基金资助项目(11771114,11971139);浙江省自然科学基金资助项目(LY21A010014)。

摘　　要：研究带模具约束的两台同型机排序问题,针对极小化工件最大完工时间的目标函数,与已有的3/2近似算法相比,增加对最大工件集的处理,得到改进算法的近似比为4/3,并给出了紧例。This paper discusses the scheduling problem on two identical parallel machines with different molds as the resource constraints.The goal is to minimize the makespan.Compared with the existing 3/2-approximation algorithms,we focus on the process of the largest job sets and present an improved algorithm with approximation ratio 4/3.A tightness instance is also provided.

关 键 词：排序问题 模具约束 近似算法 近似比 

分 类 号：O221.7[理学—运筹学与控制论]