全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

就绪时间受限的负荷单机环境下返工工件重调度方法

DOI: 10.3724/SP.J.1004.2013.02100, PP. 2100-2110

Keywords: 重调度,单机,返工,启发式算法,等待时间

Full-Text   Cite this paper   Add to My Lib

Abstract:

?研究了返工工件的单机重调度问题.在初始调度中初始工件带有不同的就绪时间,优化目标为最小化初始工件等待时间和;重调度时在满足每个初始工件最大等待时间约束情况下安排返工工件的生产,优化目标为最小化所有工件等待时间和.文中首先建立了RRSM(Reschedulingforreworksonsinglemachine)问题模型,并证明其为NP难问题.然后,提出并证明了三个RRSM问题性质,进而根据诸性质设计了求解RRSM问题的动态插入启发式(Dynamicinsertheuristic,DIH)算法.证明了应用DIH算法能在多项式时间内求得两种特殊RRSM问题的最优解.最后,分析了DIH算法解的特点,给出了最优解的判定方法,并通过算例说明了DIH算法的有效性.

References

[1]  Daniels R L, Kouvelis P. Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 1995, 41(2): 363-376
[2]  Webster S, Baker K R. Scheduling groups of jobs on a single machine. Operations Research, 1995, 43(4): 692-703
[3]  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)
[4]  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
[5]  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
[6]  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
[7]  Hall N G, Liu Z X, Potts C N. Rescheduling for multiple new orders. INFORMS Journal on Computing, 2007, 19(4): 633-645
[8]  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
[9]  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
[10]  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
[11]  Chu C. Efficient heuristics to minimize total flow time with release dates. Operations Research letters, 1992, 12(5): 321-330
[12]  Gupta S K, Kyparisis J. Single machine scheduling research. Omega, 1987, 15(3): 207-227
[13]  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
[14]  Herrmann J W. Rescheduling strategies, policies, and methods. Handbook of Production Scheduling, 2006, 89: 135-148
[15]  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
[16]  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
[17]  Hall N G, Potts C N. Rescheduling for new orders. Operations Research, 2004, 52(3): 440-453
[18]  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
[19]  Zhao C L, Tang H Y. Rescheduling problems with deteriorating jobs under disruptions. Applied Mathematical Modelling, 2010, 34(1): 238-243
[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]  Liu Min. A survey of data-based production scheduling methods. Acta Automatica Sinica, 2009, 35(6): 785-806 (刘民. 基于数据的生产过程调度方法研究综述. 自动化学报, 2009, 35(6): 785-806)

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133