A unified approach for scheduling with convex resource consumption functions using positional penalties

作者：Leyvand Yaron; Shabtay Dvir; Steiner George^*

来源：European Journal of Operational Research, 2010, 206(2): 301-312.

DOI：10.1016/j.ejor.2010.02.026

• Single machine scheduling
• Controllable processing times
• Resource allocation
• Due date assignment
• Positional penalties
• Polynomial-time algorithm

We provide a unified model for solving single machine scheduling problems with controllable processing times in polynomial time using positional penalties. We show how this unified model can be useful in solving three different groups of scheduling problems. The first group includes four different due date assignment problems to minimize an objective function which includes costs for earliness, tardiness, due date assignment, makespan and total resource consumption. The second group includes three different due date assignment problems to minimize an objective function which includes the weighted number of tardy jobs, due date assignment costs, makespan and total resource consumption costs. The third group includes various scheduling problems which do not involve due date assignment decisions. We show that each of the problems from the first and the third groups can be reduced to a special case of our unified model and thus can be solved in O(n(3)) time. Furthermore, we show how the unified model can housed repeatedly as a subroutine to solve all problems from the second group in O(n(4)) time. In addition, we also show that faster algorithms exist for several special cases.

• 出版日期2010-10-16