基于混合粒子群算法具有交货期瓶颈的作业车间调度问题

摘要/Abstract

摘要：

为了解决一类具有交货期瓶颈的作业车间调度问题，给出了基于订单优势的交货期满意度和交货期瓶颈资源确定方法，以工件拖期加权和最小为优化目标，建立了基于交货期满意度和瓶颈资源约束的作业车间调度模型;为了求解该调度模型，设计了一种基于模拟退火的混合粒子群算法，该算法采用随机工序表达方式进行编码，并在模拟退火算法中引入变温度参数来提高算法效率。通过随机仿真，分别采用PSO-SA、SA和PSO对所建立的调度模型进行求解，结果显示PSO-SA算法的广泛性好、求解效率高且算法的稳定性好，验证了模型和算法的有效性。

关键词: 作业车间, 交货期瓶颈资源, 交货期满意度, 混合粒子群算法

Abstract:

To solve a kind of job shop scheduling problem for due-time bottleneck, taking the tardiness weighted sum as the optimization objective, a model based on due-time degree of satisfaction and bottleneck resources was presented. According to the characteristics of job shop, a hybrid algorithm with particle swarm optimization and simulated annealing algorithm was proposed to solve the model. In the hybrid algorithm, a random process expression method for encoding was taken. And a dynamic temperature parameter was introduced to the simulated annealing algorithm to increase the algorithm's efficiency. The simulation was given to test the model and algorithms presented herein. And the testing results prove the method is effective.

Key words: job shop, due-time bottleneck resource, due-time degree of satisfaction, hybrid particle swarm optimization (HPSO)

中图分类号:

TP301

鲁建厦, 邓伟, 董巧英. 基于混合粒子群算法具有交货期瓶颈的作业车间调度问题[J]. 中国机械工程, 2014, 25(5): 624-629.

Lu Jiansha, Deng Wei, Dong Qiaoying. Job Shop Scheduling for Due-time Bottleneck Based on HPSO Algorithm[J]. China Mechanical Engineering, 2014, 25(5): 624-629.

参考文献

[1]顾余容. 基于交货期瓶颈的作业车间智能调度研究[D]. 杭州:浙江工业大学, 2010.
[2]李平, 顾幸生. 不确定条件下不同交货期窗口的Job shop调度[J]. 管理科学学报, 2004,7(2): 22-26.
Li Ping, Gu Xinsheng. The Job Shop Scheduling of Uncertain Different Delivery Window[J]. Journal of Management Science, 2004,7(2): 22-26.
[3]李平,顾幸生.不确定条件下不同交货期窗口的Flow Shop调度[J]. 系统仿真学报, 2004, 16(1):155-157.
Li Ping, Gu Xinsheng. The Flow Shop Scheduling of Uncertain Different Delivery Window[J]. Journal of System Simulation, 2004, 16(1):155-157.
[4]吴悦, 汪定伟. 模糊交货期窗口下极大化顾客满意数的最优调度[J]. 系统工程理论方法应用, 1999, 8(1):33-38.
Wu Yue, Wang Dingwei.Fuzzy Delivery Window under Maximization Customer Satisfaction for Optimum Scheduling[J]. Systems Engineering Theory Methodelogy Applications, 1999, 8(1):33-38.
[5]吴春辉, 周水银. 并行多机加权成套订单数极大化的混合遗传算法[J]. 系统工程理论与实践, 2006, 11(4):125-129.
Wu Chunhui, Zhou Shuiyin.A Hybrid Genetic Algorithm: Weighted Scheduling Problem to Maximize the Whole-set Orders on Parallel Machines[J]. Systems Engineering-theory & Practice, 2006, 11(4):125-129.
[6]Vinod V, Sridharan R. Simulation Modeling and Analysis of Due-date Assignment Methods and Scheduling Decision Rules in a Dynamic Job Shop Production System[J]. International Journal of Production Economics, 2011, 1(29):127-146.
[7]T’kindt V, Della Croce F. A Note on “Two-machine Flow-shop Scheduling with Rejection” and Its Link with Flow-shop Scheduling and Common Due Date Assignment[J]. Computers & Operations Research, 2012, 3(9):3244-3246.
[8]Su Nguyen, Zhang Mengjie, Johnston Mark, et al. Evolving Reusable Operation-based Due-date Assignment Models for Job Shop Scheduling with Genetic Programming[J]. Lecture Notes in Computer Science, 2012, 72(44):121-133.
[9]Hu Yanmei, Yin Minghao, Li Xiangtao. A Novel Objective Function for Job-shop Scheduling Problem with Fuzzy Processing Time and Fuzzy Due Date Using Differential Evolution Algorithm[J]. International Journal of Advanced Manufacturing Technology, 2011, 5(6):1125-1138.
[10]鲁建厦, 蒋玲玲, 李修琳. 基于混合粒子群算法求解装配线第二类平衡问题[J]. 中国机械工程, 2010, 21(4):420-423.
Lu Jiansha, Jiang Lingling, Li Xiulin. Hybrid Particle Swarm Optimization Algorithm for Assembly Line Balancing Problem-2[J]. China Mechanical Engineering, 2010, 21(4):420-423.
[11]李修琳, 鲁建厦, 柴国钟, 等. 基于混合遗传算法的混流混合车间协同调度问题[J]. 中国机械工程, 2012, 23(8):935-940.
Li Xiulin, Lu Jiansha, Chai Guozhong, et al. Hybrid Genetic Algorithm for Mixed-model Hybrid-shop Scheduling Problem[J]. China Mechanical Engineering, 2012, 23(8):935-940.
[12]贾兆红, 陈华平, 孙耀辉. 混合粒子群算法在柔性工作车间调度中的应用[J]. 系统仿真学报, 2007, 19(20):4743-4747.
Jia Zhaohong, Chen Huaping, Sun Yaohui. Hybrid Particle Swarm Optimization for Flexible Job-shop Scheduling[J]. Journal of System Simulation, 2007, 19(20):4743-4747.
[13]郭源生. 基于顾客满意度的客户订单选择[J]. 西安电子科技大学报, 2007, 17(6):36-40.
Guo Yuansheng. Options of Customer Orders Based on Customer Satisfaction[J]. Journal of Xidian University(Social Sciences Edition), 2007, 17(6):36-40.
[14]陈国初, 俞金寿, 郭伟. 两群替代微粒群优化算法及其应用[J]. 华东理工大学学报(自然科学版), 2005, 31(6):787-791.
Chen Guochu, Yu Jinshou, Guo Wei. Two Sub-swarms Substituting Particle Swarm Optimization Algorithm and Its Application[J]. Journal of East China University of Science and Technology(Natural Science Edition), 2005, 31(6):787-791.

[1]	李西兴, 杨道明, 李鑫, 吴锐, . 基于混合遗传鲸鱼优化算法的柔性作业车间自动导引车融合调度方法[J]. 中国机械工程, 2021, 32(08): 938-950，986.
[2]	李益兵1,2;黄炜星1;吴锐1. 基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究[J]. 中国机械工程, 2020, 31(11): 1344-1350,1385.
[3]	刘彩洁;徐志涛;张钦;张力菠;姚坤. 分时电价下基于NSGA-Ⅱ的柔性作业车间绿色调度[J]. 中国机械工程, 2020, 31(05): 576-585.
[4]	陈勇;程子文;姜枞聪;王亚良;王成;郦仕云. 考虑布局熵的多态性车间布局稳健优化模型与算法[J]. 中国机械工程, 2019, 30(15): 1837-1848.
[5]	杨冬婧, 雷德明. [车间调度]新型蛙跳算法求解总能耗约束FJSP[J]. 中国机械工程, 2018, 29(22): 2682-2689.
[6]	曾强, 邓敬源, 常梦辉, 张进春. [车间调度]混合工作日历下作业车间调度遗传进化方法[J]. 中国机械工程, 2018, 29(22): 2690-2702.
[7]	杨宇;黄敏;王震宇;朱启兵. 利用有限制稳定配对策略求解双目标柔性作业车间调度问题[J]. 中国机械工程, 2018, 29(14): 1743-1750.
[8]	朱传军, 邱文, 张超勇, 金亮亮. 多目标柔性作业车间稳健性动态调度研究[J]. 中国机械工程, 2017, 28(02): 173-182.
[9]	徐本柱, 吉靖, 费晓璐. 柔性作业车间中基于工序分批的调度问题与求解[J]. 中国机械工程, 2016, 27(23): 3221-3229.
[10]	朱传军, 邱文, 朱孟周, 陈光, 张超勇. 随机工时下的多目标柔性作业车间鲁棒调度问题[J]. 中国机械工程, 2016, 27(12): 1667-1672,1678.
[11]	朱传军 , 宋文家, 张超勇, 曹静 , 朱孟周. 基于维修时间窗的柔性作业车间调度优化研究[J]. 中国机械工程, 2016, 27(10): 1337-1343.
[12]	赵敏, 殷欢, 孙棣华, 郑林江, 何伟, 袁川. 基于改进人工鱼群算法的柔性作业车间调度[J]. 中国机械工程, 2016, 27(08): 1059-1065.
[13]	彭建刚, 刘明周, 张玺, 张铭鑫, 葛茂根. 基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题[J]. 中国机械工程, 2015, 26(5): 620-626.
[14]	汪俊亮, 张洁, 秦威, 银莉, 陈定方. 加工时间不确定的柔性作业车间鲁棒调度方法[J]. 中国机械工程, 2015, 26(5): 627-632.
[15]	杨宏安, 席志成, 夏常凯, 王经国. Job Shop调度问题的Minimax模型及双空间协同遗传算法[J]. 中国机械工程, 2015, 26(3): 330-338.