具有工期限制的退化工件单机排序问题

Scheduling of Single Machine with Deteriorating Jobs and Due-Date Assignment

工件具有退化效应的排序问题最近几年受到人们越来越多的关注。所谓具有退化效应的工件是指在排序中,工件的开工时间越晚其实际的加工时间就越长。讨论了一类具有工期限制的线性退化工件单机排序问题。其中线性退化工件指的是工件的实际加工时间是线性增长的函数。文中工件的实际加工时间不是固定不变的,是该工件的开始加工时间的单增函数。目标函数是使完工时间,提前完工时间和误工时间的加权和最小。给出了多项式时间的最优算法。

The scheduling problems with deteriorating jobs have received increasing attention in recent years.The jobs with deterioration means jobs processed later in the sequence require more time.In this paper,we study a single-machine scheduling problem with common due-date and linear deteriorating jobs,where linear deteriorating jobs mean that the processing time of a job is a linear increasing function of its start time.The actual processing times of jobs are not fixed.They are an increasing function of their start times.The objective is to determine the optimal due-date and schedule simultaneously to minimize the completion time,earliness and tardiness penalties.We provide a polynomial time algorithm to solve the problem.