单机下带有松弛工期的最小化总提前损失与误工损失问题

The Single-Machine Scheduling Problem with Slack Due Date to Minimize Total Early Work and Late Work

文章研究了具有松弛工期的单机排序问题,决策者需要在确定工件的工期之后确定工件的加工次序.松弛工期是工件的加工时间加上一个给定的常数,这个常数为决策变量,排序的任务是给所有工件分配松弛工期,同时使得目标函数值最小.目标函数值包括工件提前、误工和松弛工期.文章根据不同的损失系数关系,讨论松弛工期的范围,并提出了时间复杂性为O(n3P3logn)的动态规划算法.最后给出了算例分析.

This paper considers the single-machine scheduling problem with slack due date.The decision needs to determine the processing sequence of jobs when the due date of jobs is determined.Slack due date means that the due date is equal to its processing time plus a constant,where the constant is the decision variable.The aim is to assign the slack due date and minimize the objective function.The objective function includes the early work,late work and slack due date.In this paper,we discuss the range of slack due date by cost coefficients,and design a dynamic programming algorithm to solve this problem.It is proven that the optimal solution can be obtained in O(n^(3)p^(3)log n)time.Finally,a numerical example is presented to illustrate the feasibility of the algorithms.