Rescheduling with Release Time to Minimize Sum of Waiting Time Considering Waiting Constraint of Original Loads
-
摘要: 研究了返工工件的单机重调度问题.在初始调度中初始工件带有不同的就绪时间,优化目标为最小化初始工件等待时间和;重调度时在满足每个初始工件最大等待时间约束情况下安排返工工件的生产,优化目标为最小化所有工件等待时间和.文中首先建立了RRSM (Rescheduling for reworks on single machine)问题模型,并证明其为NP难问题.然后,提出并证明了三个RRSM问题性质,进而根据诸性质设计了求解RRSM问题的动态插入启发式(Dynamic insert heuristic,DIH)算法.证明了应用DIH算法能在多项式时间内求得两种特殊RRSM问题的最优解. 最后,分析了DIH算法解的特点,给出了最优解的判定方法,并通过算例说明了DIH算法的有效性.Abstract: In this paper, we consider the rescheduling problem to minimize the sum of waiting times of rework jobs and the original loads with release time on a single machine, and the waiting time of each original load is constrained by a value. The problem of rescheduling for reworks on a single machine (RRSM) is formulated and proved to be NP-hard. A dynamic insert heuristic (DIH) algorithm of polynomial-time is designed and proved with three properties. With respect to two special cases of the identical processing time of rework jobs or the machine without idle times in the original schedule, the DIH algorithm can obtain an optimal solution. A discrimination condition is proved for the optimal solution and effectiveness of the DIH algorithm is explained by cases with regard to general RRSM problems.
-
Key words:
- Rescheduling /
- single machine /
- rework /
- heuristic algorithm /
- waiting time
-
[1] Liu Min. A survey of data-based production scheduling methods. Acta Automatica Sinica, 2009, 35(6): 785-806 (刘民. 基于数据的生产过程调度方法研究综述. 自动化学报, 2009, 35(6): 785-806) [2] Daniels R L, Kouvelis P. Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 1995, 41(2): 363-376 [3] Gupta S K, Kyparisis J. Single machine scheduling research. Omega, 1987, 15(3): 207-227 [4] Webster S, Baker K R. Scheduling groups of jobs on a single machine. Operations Research, 1995, 43(4): 692-703 [5] Yan Yang, Wang Da-Zhi, Wang Ding-Wei, Ip W H, Wang Hong-Feng. Single machine group scheduling problems with the effects of deterioration and learning. Acta Automatica Sinica, 2009, 35(10): 1290-1295 [6] Zhao Yu-Fang, Tang Li-Xin. Scheduling with agreeable release times and due dates on a single continuous batch processing machine. Acta Automatica Sinica, 2008, 34(8): 957-963 (赵玉芳, 唐立新. 释放时间和工期同序的单机连续型批调度问题. 自动化学报, 2008, 34(8): 957-963) [7] Herrmann J W. Rescheduling strategies, policies, and methods. Handbook of Production Scheduling, 2006, 89: 135-148 [8] Inderfurth K, Kovalyov M Y, Ng C T, Werner F. Cost minimizing scheduling of work and rework processes on a single facility under deterioration of reworkables. International Journal of Production Economics, 2007, 105(2): 345-356 [9] Sarker B R, Jamal A M M, Mondal S. Optimal batch sizing in a multi-stage production system with rework consideration. European Journal of Operational Research, 2008, 184(3): 915-929 [10] Haji R, Haji B. Optimal batch production for a single machine system with accumulated defectives and random rate of rework. Journal of Industrial and Systems Engineering, 2012, 3(4): 243-256 [11] Wu S D, Storer R H, Chang P C. A rescheduling procedure for manufacturing systems under random disruptions. In: New Directions for Operations Research in Manufacturing. Berlin, Germany: Springer, 1992. 292-308 [12] Unal A T, Uzsoy R, Kiran A S. Rescheduling on a single machine with part-type depend setup times and deadlines. Annals of Operations Research, 1997, 70: 93-113 [13] Hall N G, Potts C N. Rescheduling for new orders. Operations Research, 2004, 52(3): 440-453 [14] Hall N G, Liu Z X, Potts C N. Rescheduling for multiple new orders. INFORMS Journal on Computing, 2007, 19(4): 633-645 [15] Yuan J J, Mu Y D. Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption. European Journal of Operational Research, 2007, 182(2): 936-944 [16] Yang B B. Single machine rescheduling with new jobs arrivals and processing time compression. The International Journal of Advanced Manufacturing Technology, 2007, 34(3): 378-384 [17] Zhao C L, Tang H Y. Rescheduling problems with deteriorating jobs under disruptions. Applied Mathematical Modelling, 2010, 34(1): 238-243 [18] Hoogeveen H, Lenté C, T'kindt V. Rescheduling for new orders on a single machine with setup times. European Journal of Operational Research, 2012, 223(1): 40-46 [19] Chu C B. A branch-and-bound algorithm to minimize total flow time with unequal release dates. Naval Research Logistics, 1992, 39(6): 859-875 [20] Graham R L, Lawler E L, Lenstra J K, Rinnooy Kan A H G. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 1979, 5: 287-326 [21] Kellerer H, Tautenhahn T, Woeginger G J. Approximability and nonapproximability results for minimizing total flow time on a single machine. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. New York, NY, USA: ACM, 1996. 418-426 [22] Chu C. Efficient heuristics to minimize total flow time with release dates. Operations Research letters, 1992, 12(5): 321-330
点击查看大图
计量
- 文章访问数: 1482
- HTML全文浏览量: 93
- PDF下载量: 949
- 被引次数: 0