具有老化效应的单机共同工期安排和工件可拒绝排序问题

Due-date Assignment and Single Machine Scheduling with Aging Effect and Rejection

研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。

This paper considers a single-machine scheduling and due date assignment problem.During the processing horizon,the processing time of a job depends on its position in a processing sequence and its aging effect and jobs also can be rejected by incurring penalties.The objective is to divide the jobs into a set of accepted and a set of rejected jobs,determine the sequence of accepted jobs and the location of maintenance activity so as to minimize the sum of the accepted jobs costs of earliness,tardiness,due date and the total penalty of the rejected jobs.We first provide a polynomial-time algorithm to solve the problem by translating it into assignment problem.We then prove a unified problem can be solved in polynomial time.Finally,we provide polynomial-time dynamic programming algorithms for the special case of the problem.