在退化维修下带有工期指派和加工时间可控的单机排序问题

摘要

讨论在一次退化维修下带有3种工期指派和加工时间可控的单机排序问题.其中机器的维修时间是维修开始时间的线性非减函数,工期指派的3种模型包括共同工期指派模型、松弛工期指派模型、无限制工期指派模型,工件的实际加工时间依赖于工件的开工时间、工件的位置以及资源分配的函数.目标是要找到机器的最优维修位置和最优排序,极小化提前时间、延误时间、工期以及资源分配的总费用.当机器的维修位置固定时,证明了该问题可以转化为指派问题；当机器的维修位置不固定时,给出了一个算法,并证明了该问题可以在O(n4)时间内求得最优解；最后以共同工期指派模型为例给出一个实例.%We study scheduling problem on a single machine with three-models of due-date assignment and controllable processing times under a deteriorating maintenance consideration.The machine maintenance duration is given as a linear nondecreasing function of its starting time,and the three due-date assignment methods include the common due date,the slack due date and the unrestricted due date.In addition,the actual processing time of a job is a function of its starting time,its position and resource allocation.The objective is to find the optimal maintenance position and the optimal sequnences to minimize the total costs which include total earliness,tardiness,due date and resource allocation costs.If the position of the maintenance activity is determined,the problem can be formulated as an assignment problem.Or else,we give a polynomial time algorithm for the problem which can be solved in O(n4) time,and at last a example for the algorithm is given.