具有随机返工且可中断的设计任务调度

doi:10.3969/j.issn.1007-7375.2019.05.008

工业工程 ›› 2019, Vol. 22 ›› Issue (5): 59-67.doi: 10.3969/j.issn.1007-7375.2019.05.008

具有随机返工且可中断的设计任务调度

王小岗, 王小明, 陈庆新, 毛宁

广东工业大学广东省计算机集成制造重点实验室, 广东广州 510006

收稿日期:2018-12-28 出版日期:2019-10-31 发布日期:2019-10-29
通讯作者: 王小明(1986-),男,江西省人,讲师,工学博士,主要研究方向为随机项目调度与监控、制造与服务系统随机建模优化等,E-mail:simonwang@gdut.edu.cn. E-mail:simonwang@gdut.edu.cn
作者简介:王小岗(1990-),男,河南省人,硕士研究生,主要研究方向为排序调度
基金资助:
国家自然科学基金资助项目（51505090，51775120，61573109，71972053，61973089）

Preemptive Scheduling of Design Tasks with Random Rework

WANG Xiaogang, WANG Xiaoming, CHEN Qingxin, MAO Ning

Provincial Key Laboratory of Computer Integrated Manufacturing, Guangdong University of Technology, Guangzhou 510006, China

Received:2018-12-28 Online:2019-10-31 Published:2019-10-29

摘要/Abstract

摘要： 随机返工和可中断特征使得设计任务调度问题异常复杂。针对该问题，采用马尔可夫决策过程理论建模，并利用动态规划方法求解使得加权拖期总成本期望最小的最优调度策略。为了应对传统动态规划面临的维数灾，引入多规则组合算法来限制每个状态下的可选行动数量，从而高效获得次优调度策略。实验结果表明，传统动态规划仅能够求解小规模问题，而所提出的多规则组合方法则有效权衡了优化效果和求解效率，更具实用价值。

关键词: 设计任务, 随机返工, 可中断, 马尔可夫决策过程, 动态规划, 多规则组合

Abstract: The characteristics of random rework and preemption make the design task scheduling problem become very difficult. To address this issue, a mathematical model is constructed based on Markov decision processes. An optimal solution that minimize the expected total weighted tardiness cost is obtained by the dynamic programming. To deal with the curse of dimensionality that faced by traditional dynamic programming, a method based on multi-rule combination is employed to reduce the amount of feasible actions in each state, which can efficiently obtain a suboptimal solution. Experimental results show that the traditional dynamic programming can only handle some very small-scale problem instances, while the proposed multi-rule combination method effectively balances the optimization effect and computational efficiency, which is more practical.

Key words: design task, random rework, preemption, Markov decision processes, dynamic programming, multi-rule combination

中图分类号:

TP391

王小岗, 王小明, 陈庆新, 毛宁. 具有随机返工且可中断的设计任务调度[J]. 工业工程, 2019, 22(5): 59-67.

WANG Xiaogang, WANG Xiaoming, CHEN Qingxin, MAO Ning. Preemptive Scheduling of Design Tasks with Random Rework[J]. Industrial Engineering Journal , 2019, 22(5): 59-67.

参考文献

[1] 张永健, 钟诗胜, 王体春. 不确定环境下产品设计项目过程执行仿真[J]. 计算机集成制造系统, 2012, 18(2):269-275 ZHANG Yongjian, ZHONG Shisheng, WANG Tichun. Process execution simulation for product development project under uncertainty[J]. Computer Integrated Manufacturing Systems, 2012, 18(2):269-275
[2] 焦勇清, 王小明. 基于仿真模型的带随机返修模具设计项目完工时间预测[J]. 模具工业, 2018, 44(9):20-27 JIAO Yongqing, WANG Xiaoming. Prediction of completion time of die design project with random repair based on simulation model[J]. Die & Mould Industry, 2018, 44(9):20-27
[3] GARTNERT, ROHLEDER N, SCHLICK C M. Simulation of product change effects on the duration of development processes based on the DSM[J]. Journal of Food Science, 2008, 53(6):1778-1781
[4] WANG X M, LEUS R, CREEMERS S, et al. A CTMDP-based exact method for RCPSP with uncertain activity durations and rework[C/OL]. (2018-05-26). https://link.springer.com/chapter/10.1007/978-3-319-89920-6_74.
[5] LUH P B, LIU F, MOSER B. Scheduling of design projects with uncertain number of iterations[J]. European Journal of Operational Research, 1999, 113(3):575-592
[6] 陈武一, 王小明. 具有返工过程的动态任务调度方法[J]. 模具工业, 2018, 44(11):9-14 CHEN Wuyi, WANG Xiaoming. Dynamic task scheduling method with rework process[J]. Die & Mould Industry, 2018, 44(11):9-14
[7] BROWNING T R, YASSINE A A. Managing a portfolio of product development projects under resource constraints[J]. Decision Sciences, 2016, 47(2):333-372
[8] YASSINE A A, MOSTAFA O, BROWNING T R. Scheduling multiple, resource-constrained, iterative, product development projects with genetic algorithms[J]. Computers & Industrial Engineering, 2017, 107:39-56
[9] 郭艳东, 王庆, 黄敏, 等. 就绪时间受限的负荷单机环境下返工工件重调度方法[J]. 自动化学报, 2013, 39(12):2100-2110 GUO Yandong, WANG Qing, HUANG Min, et al. Reworking method for reworking workpieces in a single machine environment with limited readiness time[J]. ACTA AUTOMATICA SINICA, 2013, 39(12):2100-2110
[10] ESKANDARI H, HOSSEINZADEH A. A variable neighborhood search for hybrid flow-shop scheduling problem with rework and set-up times[J]. Journal of The Operational Research Society, 2014, 65(8):1221-1231
[11] SHIN J H. A dispatching algorithm considering process quality and due dates:an application for re-entrant production lines[J]. International Journal of Advanced Manufacturing Technology, 2015, 77(1-4):249-259
[12] RAGHAVAN V A, YOON S W, SRIHARI K. Heuristic algorithms to minimize total weighted tardiness with stochastic rework and reprocessing times[J]. Journal of Manufacturing Systems, 2014, 37:233-242.
[13] RAGHAVAN V A, YOON S W, SRIHARI K. A modified genetic algorithm approach to minimize total weighted tardiness with stochastic rework and reprocessing times[J]. Computers & Industrial Engineering, 2018, 123:42-53
[14] 陈建国, 舒辉, 余平祥. 随机返工及重加工情形下的Job-Shop调度问题[J]. 工业工程, 2015, 18(5):127-133, 147 CHEN Jianguo, SHU Hui, YU Pingxiang. A research on job-shop scheduling in stochastic rework and reprocessing situation[J]. Industrial Engineering Journal, 2015, 18(5):127-133, 147
[15] LAWLER E L. A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs[J]. Annals of Operations Research, 1990, 26(1):125-133
[16] LIAW C F. An efficient tabu search approach for the two-machine preemptive open shop scheduling problem[J]. Computers & Operations Research, 2003, 30(14):2081-2095
[17] 程贞敏, 张喜娟, 李洪兴. 工件带准备时间的平行机调度问题的一个近似算法[J]. 北京师范大学学报(自然科学版), 2009, 45(4):350-353 CHENG Zhenmin, ZHANG Xijuan, LI Hongxing. An approximation algorithm for parallel machine scheduling problem[J]. Journal of Beijing Normal University (Natural Science), 2009, 45(4):350-353
[18] 周华奇, 鲁鸣鸣, 朱洪. 有不同中断时间代价的一致并行抢先调度问题[J]. 计算机研究与发展, 2009, 42(3):507-513 ZHOU Huaqi, LU Mingming, ZHU Hong. Parallel preemptive scheduling with different interruption time costs[J]. Computer Research and Development, 2009, 42(3):507-513
[19] 展勇, 邱长华, 祝海涛. 基于网络流的多并行机可中断开放车间调度算法[J]. 计算机集成制造系统, 2011, 17(5):990-996 ZHAN Yong, QIU Changhua, ZHU Haitao. An open shop scheduling algorithm for multiple parallel machines based on network flow[J]. Computer Integrated Manufacturing Systems, 2011, 17(5):990-996
[20] DEMEULEMEESTER E L, HERROELEN W S. An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem[J]. European Journal of Operational Research, 1996, 90(2):334-348
[21] MOUKRIM A, QUILLIOT A, TOUSSAINT H. An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem based on minimal interval order enumeration[J]. European Journal of Operational Research, 2015, 244(2):360-368
[22] PETEGHEM V V, VANHOUCKE M. A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem[J]. European Journal of Operational Research, 2010, 201(2):409-418
[23] PUTERMAN M L. Markov decision processes:discrete stochastic dynamic programming[M]. USA:John Wiley & Sons, 2009.
[24] POWELL W B. Approximate dynamic programming:solving the Curses of dimensionality[M]. 2nd ed. USA:John Wiley & Sons, 2011.
[25] 王小明. 基于Markov理论的模具项目群监控方法[D]. 广州:广东工业大学, 2014. WANG Xiaoming. Markov theory-based methods for monitoring mold projects[D]. Guangzhou:Guangdong University of Technology, 2014.
[26] VEPSALAINEN A P J, MORTON T E. Priority rules for Job Shops with weighted tardiness costs[J]. Management Science, 1987, 33(8):1035-1047
[27] WANG X M, CHEN Q X, MAO N, et al. Proactive approach for stochastic RCMPSP based on multi-priority rule combinations[J]. International Journal of Production Research, 2015, 53(4):1098-1110
[28] RAGATZ G L, MABERT V A. A simulation analysis of due date assignment rules[J]. Journal of Operations Management, 1984, 5(1):27-39

具有随机返工且可中断的设计任务调度

Preemptive Scheduling of Design Tasks with Random Rework

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	吴晓黎, 杨海欣, 刘雪洁. 订单式生产下汽车零配件企业采购决策研究[J]. 工业工程, 2021, 24(5): 63-71,94.
[2]	徐沙, 李彦瑾, 罗霞. 基于旅客购票行为仿真的高铁票价动态调整[J]. 工业工程, 2018, 21(4): 62-67.
[3]	初梓豪, 徐哲, 李明, 顾坤. 随机多模式资源均衡问题建模与求解[J]. 工业工程, 2017, 20(3): 95-105.
[4]	杨亚璪1,2，李鹏飞1，陈坚1，郝小妮3. 基于顾客选择行为的租赁车辆存量动态控制稳健模型[J]. 工业工程, 2016, 19(4): 140-145.
[5]	潘海侠，王晶. 服务系统中多阶段动态服务匹配模型及优化算法研究[J]. 工业工程, 2012, 15(5): 112-117.
[6]	王江沄，王纟委. 柔性契约机制下外向型制造商的多阶段采购策略分析[J]. 工业工程, 2011, 14(3): 70-73.