具有恶化效应、资源分配、速率修正和松弛工期的排序问题

Scheduling Problems with Deterioration Effects,Resource Allocation,Rate-Modifying Activity and Slack Due Date Assignment

研究带有松弛工期指派的单机排序问题,工件的实际加工时间同时受到恶化效应、凸资源分配与一次机器速率修正活动的影响。为确定工件的最优排序、速率修正活动的最优位置、最优的公共容许流和最优的资源分配量,使2个约束目标函数极小化。第1个目标函数是在满足资源总量有限的条件下,极小化总惩罚费用,即提前、延误、公共容许流和时间表长的加权和;第2个目标函数是在总惩罚有限的条件下,极小化资源消耗总费用。将上述问题分别转化为指派问题。当速率修正活动位于不同的位置时,选取使得目标函数最小的解为最优解。对2个问题分别给出多项式时间算法,算法的复杂度为O(n^(4)),其中n为工件的数量。用数值算例分别验证2个算法,说明给出的求解算法比较有效。

Single machine scheduling problem with slake due date assignment is studied.The actual processing time of a job is determined by deterioration effects,convex resource allocation and a rate-modifying activity on the machine.The problem is to determine the optimal job sequence,the optimal position of the rate-modifying activity,the optimal common flow allowance and the amount of resource allocation such that the two constrained optimization objective cost functions are minimized.One is the weighted penalties for the sum of earliness,tardiness,common flow allowance and maximum completion time subject to an upper bound on the total resource cost,the other is minimizing the total resource cost subject to an upper bound on the total penalty cost.Transform the two problems into assignment problems.When the rate-modifying activity is located in different positions,select the optimal solution such that minimizes the objective function.It is proved that these problems remain polynomial solvable under the proposed algorithms and the time complexity are O(n~4),where n is the number of jobs.Numerical examples show that the proposed algorithms are effective.