可变加工时间和维护的松弛交货期与凸资源分配单机排序问题

Single Machine Scheduling and Slack Due-Date Assignment and Convex Resource Allocation Problem with Variable Job Processing Time and Maintenance

摘要: 本文研究带有可变加工时间和维护的松弛交货期与凸资源分配的单机排序问题。工件的实际加工时间是所分配的不可再生资源量和与工件位置、开始时间有关的退化效应的函数。在规划时间内最多允许执行一次维护活动。确定最优工件排序、最优公共松弛时间、最优维护位置和最优资源分配方案，使得由工件的提前惩罚、延误惩罚、交货期公共松弛时间、资源分配费用、最大完工时间和总完工时间构成的总费用最小。根据优化的相关知识，将问题转化为匹配问题，证明了该问题在多项式时间内是可解的，给出了多项式时间最优算法。

Abstract: This paper studies a single machine scheduling and slack due-date assignment and convex resource allocation problem with variable job processing times and maintenance. The actual processing time of a job is a function of the non-renewable resource amount allocated, position-dependent and starting time-dependent deterioration effect. At most, one maintenance is allowed throughout the planning time. The objective is to determine the optimal job schedule, optimal common slack time, optimal maintenance position and optimal resource allocation to minimize the total costs of the earliness and tardiness of the jobs, the common slack time, the cost of resource allocation, the makespan and the total completion time. According to the related knowledge of optimization, we show that the problem is polynomial solvable by transforming it into a matching problem. We present a polynomial time optimal algorithm to solve the problem.