运筹学学报 ›› 2013, Vol. 17 ›› Issue (4): 56-62.

• 运筹学 • 上一篇    下一篇

基于重新排序的退化工件最小化总延误时间问题

许小艳1, 慕运动1,*, 郝赟1   

  1. 1. 河南工业大学理学院, 郑州 450001
  • 出版日期:2013-12-15 发布日期:2013-12-15
  • 通讯作者: 慕运动 E-mail:muyundong@163.com
  • 基金资助:

    河南省自然科学基金 (No. 112300410078), 河南省教育厅自然科学基金 (No. 2011B110008)

Minimize total lateness with  deteriorating jobs based on rescheduling problem

XU Xiaoyan, MU Yundong, HAO Yun     

  1. 1.  College of Science, Henan University of Technology, Zhengzhou 450001, China
  • Online:2013-12-15 Published:2013-12-15

摘要: 考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数. 重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位. 研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率alpha_j非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法.

关键词: 序列错位, 截止日期, 总延误时间, 实际加工时间

Abstract: In this paper, we consider two single machine rescheduling problems with deteriorating jobs under sequence disruptions, the actual processing time of a job is a linear function of the starting time for deteriorating job. Rescheduling means that a set of original jobs has already been scheduled to minimize some classical objective, then a new set of jobs arrives and creates a disruption. We consider the rescheduling problem to minimize the total lateness under a limit of the sequence disruption for deteriorating job. We research the properties of feasible schedules and optimal schedules for two problems, the jobs in the set of original jobs or new jobs are ordered by non-decreasing order of the processing rate alpha_j. For each problem, the polynomial algorithm is proposed by sorting by stages or dynamic programming method, respectively.

Key words: sequence disruption, deadline, total lateness, actual processing time

中图分类号: