[1]时凌,张琼,龙彩燕.带单服务器的流水作业排序问题的复杂性[J].延边大学学报(自然科学版),2022,(04):332-335.
　SHI Ling,ZHANG Qiong,LONG Caiyan.Complexity for flow - shop scheduling problems with a single server[J].Journal of Yanbian University,2022,(04):332-335.
点击复制

带单服务器的流水作业排序问题的复杂性

《延边大学学报(自然科学版)》[ISSN:1004-4353/CN:22-1191/N] 卷: 期数: 2022年04期 页码: 332-335 栏目: 应用科学研究 出版日期: 2022-12-30
Title:
Complexity for flow - shop scheduling problems with a single server
文章编号:
1004-4353(2022)04-0332-04
作者:
时凌;  张琼;  龙彩燕
(广州工商学院通识教育学院,广东广州510850)
Author(s):
SHI Ling;  ZHANG Qiong;  LONG Caiyan
(Institute of General Education, Guangzhou College of Technology and Business, Guangzhou 510850, China)
关键词:
流水作业排序问题;  总完工时间;  单服务器;  最坏性能比
Keywords:
flow - shop scheduling problem;  total completion time;  a single server;  worst case ratio
分类号:
O223
文献标志码:
A
摘要:
研究了一个带单服务器且加工时间相等的两机流水作业排序问题,其目标函数是使总完工时间达到最小.研究表明,该流水作业排序问题是强NP- 困难的.针对该流水作业排序问题构造了一种新的加工顺序,并证明该加工顺序的紧界为7/6.
Abstract:
We consider the problem of two - machine flow - shop scheduling with a single server and equal processing times, the objective function is to minimize total completion time.We show that this problem is NP - hard in the strong sense and present a busy schedule for it with worst case ratio 7/6, and the bound is tight.

参考文献/References:

[1] LAWER E L, LENSTRA J K, RINNOOY KAN A H G, et al.Sequencing and Scheduling: Algorithms and Complexity[C]//Handbooks in Operation Research and Management Science. Amsterrdem: Logistics of Production and Inventory, 1993,4:445 - 522.
[2] LENSTRA J K, RINNOOY KAN A H G, BRUCKER P.Complexity of machine scheduling problem[J].Annual of Discrete Mathematics, 1977,1:343 - 362.
[3] LIM A, RODRIGNES B, WANG C X.Two - machine flow shop problems with a single server[J].Journal of Scheduling, 2006,9:515 - 543.
[4] CHENG T C E, KOWLOON H K, KOVALYOV M Y, et al.Scheduling a single server in a two - machine flow shop[J].Computing, 2014,70:167 - 180.
[5] 苏纯洁,姚恩瑜.带服务器的Flow shop问题[J].浙江大学学报(理学版),2000,27(4):382 - 387.
[6] 陈荣军,唐国春.费用有限的柔性两机自由作业与流水服务业排序[J].数学的实践与认识,2022,52(4):12 - 18.
[7] GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematical Operation Research, 1976,1(2):117-129.
[8] BRUCKER P, KNUST S, WANG G Q, et al.Complexity of results for flow - shop problems with a single server[J].European Journal Operation Research, 2005,165(2):398 - 407.
[9] 时凌,龙彩燕,张琼.使总完工时间达到最小的流水作业排序问题[J].西南民族大学学报(自然科学版),2020,45(6):638 - 642.
[10] GILMORE P C, GOMORY R E.Sequencing a one - state variable machine: A solvable case of the traveling salesman problem[J].Operations Research, 1996,12:655 - 679.L1,1

备注/Memo

收稿日期: 2022-08-28
基金项目: 国家自然科学基金(61763009); 广州工商学院院级科研课题立项项目(KA201831); 广州工商学院校级科研项目(KAZX2021008)
作者简介: 时凌(1959—),男,教授,研究方向为组合最优化.

更新日期/Last Update: 2022-12-30