کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
478653 | 1446118 | 2010 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A unified approach for scheduling with convex resource consumption functions using positional penalties A unified approach for scheduling with convex resource consumption functions using positional penalties](/preview/png/478653.png)
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(n3)O(n3) time. Furthermore, we show how the unified model can be used repeatedly as a subroutine to solve all problems from the second group in O(n4)O(n4) time. In addition, we also show that faster algorithms exist for several special cases.
Journal: European Journal of Operational Research - Volume 206, Issue 2, 16 October 2010, Pages 301–312