English

运筹学学报

• 运筹学 • 上一篇    下一篇

带有运输且加工具有灵活性的无等待流水作业排序问题

仲维亚1,*  马晓茹2   

  1. 1. 上海大学管理学院, 上海 200444; 2. 上海大学理学院, 上海 200444
  • 收稿日期:2015-11-27 出版日期:2016-12-15 发布日期:2016-12-15
  • 通讯作者: 仲维亚 wyzhong@shu.edu.cn
  • 基金资助:

    国家自然科学基金(Nos. 11571221, 11301327)

A no-wait flowshop scheduling problem with processing flexibility and transportation

ZHONG Weiya1,*  MA Xiaoru2   

  1. 1. School of Management, Shanghai University, Shanghai 200444, China; 2. College of Sciences, Shanghai University, Shanghai 200444, China
  • Received:2015-11-27 Online:2016-12-15 Published:2016-12-15

PDF

415

摘要：

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.

关键词: 排序, 运输, 流水作业, 近似算法

Abstract:

This paper addresses the performance of scheduling algorithms for a two-stage no-wait flowshop scheduling problem with processing flexibility and transportation, where each stage has one machine. Each job, composed of two operations, must be processed through the two stages without waiting time. We propose two approximation algorithms. The first algorithm is list scheduling and the second schedules the jobs in non-decreasing order of the total processing time of each job's two operations. We show that the worst case ratio of the algorithms is no more than 5/2 and 2, respectively. At last, we conduct numerical experiments to compare the performance of the algorithms. For the cases with different value of the parameters, we generate several instances. For every instance, the ratio of the algorithm's objective value and the optimal solution's objective value is obtained. For each case, the maximum, minimum and average value of the instances' ratio are obtained to analyze the performance of the two algorithms.

Key words: scheduling, transportation, flowshop, approximation algorithm