一个带退化工件的单机准时生产制问题  

Just-in-time on single machine scheduling problem with deteriorating jobs

作　　者：刘静[1] 闵啸[1] 

机构地区：[1]嘉兴学院数学与信息工程学院数学系,浙江嘉兴314001

出　　处：《浙江大学学报（理学版）》2010年第1期34-37,45,共5页Journal of Zhejiang University（Science Edition）

基　　金：嘉兴学院重点科研课题基金项目资助(70106005)

摘　　要：研究带退化工件的单机排序问题,即工件的加工时间是其开始加工时间的线性递增函数,且不同的工件具有不同的退化率.要求为所有工件寻找一共同的最优交货期和最优序,以极小化这些工件的共同交货期、超前罚和迟后罚之和.给出了一O(nlogn)时间的最优算法.One single machine scheduling problem with deteriorating jobs is studied, which means the jobs whose processing times are an increasing liner function of their start times, and the different job deterioration are inequality for all jobs. The problem is to determine an optimal common due-date and schedule so as to minimize the sum of due- date, earliness and tardiness penalties. An O（n logn） time algorithm is given to solve this problem.

关 键 词：单机排序 共同交货期 退化工件 准时 多项式时间算法 

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