文献类型：期刊文献

中文题名：平行三阶段流水作业问题的近似算法

英文题名：An Approximation Algorithm for the Parallel Three-Stage Flowshop Scheduling

作者：曹移林[1];余炜[1]

机构：[1]华东理工大学数学系

年份：2019

卷号：45

期号：6

起止页码：989

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;Scopus;北大核心:【北大核心2017】；CSCD:【CSCD_E2019_2020】；

基金：中央高校基本科研业务费（22220184028）

语种：中文

中文关键词：流水作业;排序;近似算法

外文关键词：flowshop;scheduling;approximation algorithm

摘要：研究了n个三阶段工件在m个流水车间进行加工的排序问题,目标为最小化最大完工时间。当m是定值时,该问题是NP困难;当m>2时,问题是强NP困难。将问题分解成3种情形,情形1给出了7/3-1/(3m)的近似比;情形2给出了一个3的近似比;情形3给出了近似比为23/6-1/(3m)。结合3种情形,最终给出了性能比为23/6-1/(3m)的算法。
The problem that schedules n three-stage jobs on m three-stage flowshops with the objective of minimizing the makespan was studied. When m is fixed, the problem is NP-hard;When m is arbitrary larger than 2, the problem is strongly NP-hard. For this problem, the present work is divided into three situations for discussion: In case1, we gave an approximate ratio of 7/3-1/(3m);in case 2, we gave an approximate ratio of three;while in case three, there was an approximate ratio of 23/6-1/(3m). Finaly we gave an approximation algorithm with a worst case ratio of 23/6-1/(3m).