English

应用科学学报 ›› 2003, Vol. 21 ›› Issue (2): 141-145.

• 论文 • 上一篇    下一篇

单机作业在成组加工下的极小迟后范围问题

程明宝, 孙世杰, 何龙敏   

  1. 上海大学数学系 上海 200436
  • 收稿日期:2002-04-03 修回日期:2002-09-29 出版日期:2003-06-10 发布日期:2003-06-10
  • 作者简介:程明宝(1972-),男,湖南新田人,硕士生;孙世杰(1945-),男,上海人,教授,博导.

Minimizing the Range of Lateness on a Single Machine with the Workpieces Processed in Batches

CHENG Ming-bao, SUN Shi-jie, HE Long-min   

  1. Department of Mathematics, Shanghai University, Shanghai 200436, China
  • Received:2002-04-03 Revised:2002-09-29 Online:2003-06-10 Published:2003-06-10

PDF

116

被引次数

12

摘要： 有时刻零到达的n个工件需在同台机器上加工,工件具各自所需的加工时间和应交工时间,这些工件分属b个不同组。加工时,同组工件必须一起或连续或同时加工。要求适当排列这些工件,包括各组工件间的排列和各组中工件的排列以使各工件的迟后范围达到极小。对这样一个成组加工排序问题,文中证得了一些性质并给出了伪多项式时间算法。

关键词: 排序, 成组加工, 迟后范围

Abstract: There are n workpieces to be processed at time zero. The length of time needed for processing them varies with each workpiece. The workpieces are divided into b batches, and all the workpieces in the same batch must be processed together, successively or at same time. The problem under consideration is to minimize the range of lateness. To solve such a scheduling problem, this paper determines some properties and constructs corresponding pseudopolynomial algorithms.

Key words: scheduling, processed in batches, range of the lateness

中图分类号: