English

应用科学学报 ›› 1998, Vol. 16 ›› Issue (1): 18-23.

• 论文 • 上一篇    下一篇

单机分批加工最大迟后问题的一个多项式时间算法

孙世杰1, Andrews Boadi1, 刘朝晖2   

  1. 1. 上海应用数学与计算数学研究所;
    2. 华东理工大学
  • 收稿日期:1996-03-01 修回日期:1996-12-19 出版日期:1998-03-31 发布日期:1998-03-31
  • 作者简介:孙世杰:教授,上海应用数学与计算数学研究所,上海 201800
  • 基金资助:
    国家自然科学基金

A Polynomial Time Algorithm for Maximum Lateness in Single Machine Scheduling with Batching

SUN SHIJIE1, ANDREWS BOADI1, LIU ZHAOHUI2   

  1. 1. Shanghai Institute on Applied Mathematics and Computation, Shanghai 201800;
    2. East China University of Science and Technology, Shanghai 200237
  • Received:1996-03-01 Revised:1996-12-19 Online:1998-03-31 Published:1998-03-31

PDF

71

被引次数

3

摘要： 文中考虑下述单机分批问题:对时刻零同时到达的n个工件需分成若干批在同台机器上加工,同批工件加工时相邻,任一工件的完工时间为所在批中全部工件完工时的时间,机器每加工一批工件需一相同的调整时间.文中以工件的最大迟后为目标函数,对工件加工顺序预先给定和可任意时的最优分批分别给出了多项式时间算法.

关键词: 排序, 分批, 多项式时间算法, 最大迟后

Abstract: N jobs arrive at same time and need to be processed in batches by the same machine. The jobs in the same batch are processed successively and the completion time of all the jobs in the same batch is defined as the completion time of the batch they belong to. There exists a set up time whenever the machine begins to process a new batch. Taking the maximum lateness as objective function, this paper develops a polynomial time algorithms for the processing sequence of the n jobs given or not given.

Key words: batch, polynomial time algorithm, scheduling, maximum lateness