PDF(570 KB)
PDF(570 KB)
PDF(570 KB)
释放时间具有凸减函数约束的单机调度问题
Single machine scheduling problem with release dates under the constraint of convex decreasing functions
研究了作业释放时间具有凸减资源消耗函数约束的单机调度问题, 调度的目标是在限定Makespan的条件下使得作业消耗资源总量最小化. 对于此类强NP-hard问题, 定义了作业右移和左移两种基本运算以及交换和插入两种邻域生成方式, 并在此基础上构造了模拟退火算法. 为评价算法的性能, 将此问题松弛成指派问题, 从而用匈牙利方法得到松弛问题的最优解, 并进一步改进下界的质量. 实验表明所构造的模拟退火算法能够在合理的时间内提供高质量的满意解.
This paper considers a single machine scheduling problem, in which the release dates of the jobs are convex decreasing functions of the consumed resource. The objective is minimizing the total resource consumption with a limited Makespan. For the NP-hard problem in the strong sense, two basic operators, left-move and right-move, and two neighborhood generation methods, insert and swap, are defined to build a simulated annealing algorithm. To evaluate the accuracy of the proposed algorithm, the problem is relaxed to an assignment problem to obtain a lower bound by Hungary method. The computational results show that the presented simulated annealing algorithm can yield high-quality solutions for the considered scheduling problem.
调度 / 单机 / Makespan / 资源分配 / 释放时间 {{custom_keyword}} /
scheduling / single machine / Makespan / resource allocation / release dates {{custom_keyword}} /
[1] Vickson R G. Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine[J]. Operations Research, 1980, 28: 1155-1167.
[2] Vickson R G. Two single machine sequencing problems involving controllable job processing times[J]. AIIE Transactions, 1980, 12(3): 258-262.
[3] Van Wassenhove L, Baker K R. A bicriterion approach to time/cost trade-offs in sequencing[J]. European Journal of Operational Research, 1982, 11: 48-54.
[4] Janiak A, Janiak W, Lichtenstein M. Resource management in machine scheduling problems: A survey[J]. Decision Making in Manufacturing and Services, 2007, 1(2): 59-89.
[5] Shabtay D, Steiner G. A survey of scheduling with controllable processing times[J]. Discrete Applied Mathematics, 2007, 155: 1643-1666.
[6] Nowicki E, Zdrzalka S. A survey of results for sequencing problems with controllable processing times[J]. Discrete Applied Mathematics, 1990, 26: 271-287.
[7] Janiak A. Single machine scheduling problem with common deadline and resource dependent release dates[J]. European Journal of Operational Research, 1991, 53: 317-325.
[8] Janiak A. Single machine sequencing with linear models of release dates[J]. Naval Research Logistics, 1998, 45: 99-113.
[9] Li K, Yang S L, Ren M L. Single machine scheduling problem with resource dependent release dates to minimize total resource consumption[J]. International Journal of Systems Science, 2011, 42(10): 1811-1820.
[10] Li C L. Scheduling to minimize the total resource consumption with a constraint on the sum of completion times[J]. European Journal of Operational Research, 1995, 80: 381-388.
[11] Choi B C, Yoon S H, Chung S J. Single machine scheduling problems with resource dependent release dates[J]. Computers & Operations Research, 2007, 34: 1988-2000.
[12] Ventura J A, Kim D, Garriga F. Single machine earliness-tardiness scheduling with resource-dependent release dates[J]. European Journal of Operational Research, 2002, 142(1): 52-69.
[13] Monma C L, Schrijver A, Todd M J, et al. Convex resource allocation problems on directed acyclic graphs: Duality, complexity, special cases, and extensions[J]. Mathematics of Operations Research, 1990, 15(4): 736-748.
[14] Shabtay D. Single and a two-resource allocation algorithms for minimizing the maximal lateness in a single machine-scheduling problem[J]. Computers & Operations Research, 2004, 31(8): 1303-1315.
[15] Shabtay D, Kaspi M. Parallel machine scheduling with a convex resource consumption function[J]. European Journal of Operational Research, 2006, 173(1): 92-107.
[16] Kaspi M, Shabtay D. A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates[J]. Computers & Operations Research, 2006, 33: 3015-3033.
[17] Cheng T C E, Janiak A. Resource optimal control in some single-machine scheduling problems[J]. IEEE Transactions on Automatic Control, 1994, 39(6): 1243-1246.
[18] Zhao C L, Tang H Y. Single machine scheduling problems with deteriorating jobs[J]. Applied Mathematics and Computation, 2005, 161: 865-874.
[19] 赵传立, 唐恒永. 一类资源约束单机排序问题[J]. 系统工程学报, 2004, 19(5): 451-456.Zhao C L, Tang H Y. Resource constrained single machine scheduling problem[J]. Journal of Systems Engineering, 2004, 19(5): 451-456.
[20] 杨晓坡. 线性减少加工时间的资源约束单机排序问题[J]. 系统工程与电子技术, 2006, 28(5): 708-711.Yang X B. Resource constrained single machine scheduling problem with linearly decreasing processing times[J]. Systems Engineering and Electronics, 2006, 28(5): 708-711.
[21] Metropolis N, Rosenbluth A, Resenbluth M, et al. Equation of state calculations by fast computing machines[J]. Journal of Chemical Physics, 1953, 21: 1087-1092.
[22] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing[J]. Science, 1983, 220: 671-680.
[23] Zhang R, Wu C. A hybrid immune simulated annealing algorithm for the job shop scheduling problem[J]. Applied Soft Computing, 2010, 10: 79-89.
[24] Figielska E. A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources[J]. Computers & Industrial Engineering, 2009, 56: 142-151.
[25] Li K, Yang S L, Ma H W. A simulated annealing approach to minimize the maximum lateness on uniform parallel machines[J]. Mathematical and Computer Modelling, 2011, 53: 854-860.
[26] Chu C. A branch and bound algorithm to minimize total tardiness with different release dates[J]. Naval Research Logistics, 1992, 39: 265-283.
国家自然科学基金(71101040, 71131002, 71001032); 安徽省自然科学基金(11040606Q27);高等学校博士学科点专项科研基金(20120111120013); 武汉大学软件工程国家重点实验室开放基金(SKLSE2012-09-10)
/
| 〈 |
|
〉 |
