具有退化工件和工期窗口安排的排序问题  

Common Due-window Assignment and Scheduling Problems with Deteriorating Jobs

作　　者：刘春来[1] 王建军[1] 赵传立[2] 

机构地区：[1]大连理工大学系统工程研究所,辽宁大连116023 [2]沈阳师范大学数学与系统科学学院,辽宁沈阳110034

出　　处：《运筹与管理》2015年第4期116-121,共6页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(71271039;70902033);教育部"新世纪优秀人才支持计划"项目(NCET-13-0082);中央高校基本科研业务费专项资金资助项目(DUT14YQ211)

摘　　要：针对具有退化工件的排序模型,考虑了单机排序和两台机器流水作业的工期窗口安排问题,在这一模型中,工件的加工时间是与其开工时间和退化率有关的一个线性函数。目标是找到一个最优排序和确定工期窗口的开始时间及大小以便最小化所有工件的费用函数,费用函数由四部分组成:提前、延误、工期窗口开始时间和工期窗口大小。对所研究的单机问题,详细地讨论了符合现实情况的几种类型问题,并得到了问题的最优解;对两台机器流水作业问题,给出了多项式算法。This paper is devoted to a scheduling problem with simple linear deterioration, that is, the processing time of a job is a simple linear function of its starting time and its deterioration rate. We consider the common due-window assignment problem for the single machine and two machine flow shop. The goal is to schedule the jobs and the due-window so as to minimize the highest cost among all the jobs. The objective function contains four cost components： earliness, tardiness, due-window starting time and size. By analyzing the properties of the optimal schedule, we obtain the due-window starting time and size. For the single machine and two-machine flow shop problems, we present a polynomial time solution respectively. Moreover, some special cases of the single machine are also discussed in detail.

关 键 词：排序 工期窗口 退化工件 提前-延误 

分 类 号：O223[理学—运筹学与控制论]