English

应用科学学报 ›› 2004, Vol. 22 ›› Issue (2): 247-251.

• 论文 • 上一篇    下一篇

两台机器流水作业中带成组加工的最大迟后问题

陈跃, 孙世杰, 宋政芳, 何龙敏   

  1. 上海大学数学系 上海 200436
  • 收稿日期:2003-03-19 修回日期:2003-09-01 出版日期:2004-06-30 发布日期:2004-06-30
  • 作者简介:陈跃(1978-),男,浙江杭州人,硕士生;孙世杰(1945-),男,上海人,教授,博导.

Minimizing the Maximum Lateness on a Two Machine Flowshop with Batch Processors

CHEN Yue, SUN Shi-jie, SONG Zheng-fang, HE Long-min   

  1. Department of Mathematics, Shanghai University, Shanghai 200436, China
  • Received:2003-03-19 Revised:2003-09-01 Online:2004-06-30 Published:2004-06-30

PDF

65

被引次数

10

摘要： 考虑分批加工中的流水作业问题:且工件在两台机器间作成批转移,目标函数为Lmax.文中指出该问题为NP-hard后给出了其多项式可解的特例并构造了相应的动态规划算法.

关键词: 多项式可解, 批处理机, 最大迟后, 强NP-hard, 排序

Abstract: This paper considers the following problem:n jobs need to be processed on two machines (M1,M2) successively. The deadline for job j is dj, and the processing times of job j on M1, M2 are aj, bj, respectively. Both machines are batch processors. This means n jobs are grouped into several batches on Mi, i=1,2, respectively, and the machines process the jobs in same batch simultaneously. The processing time of a batch is equal to the longest processing time of all the jobs in this batch. Thus all the jobs in same batch are processed in the same length of time on the given machine, and the jobs will be also shifted in batches. We take the maximum lateness as our objec function for minimization. After pointing out that this scheduling problem is NP-hard, we give some special cases that can be solved in polynomial time and construct the corresponding dynamic programming.

Key words: scheduling, maximum lateness, polynomial time algorithm, batch processor, strong NP-hard