基于批量划分的无等待流水车间订单接受问题研究

工业工程 ›› 2014, Vol. 17 ›› Issue (1): 44-49.

基于批量划分的无等待流水车间订单接受问题研究

北京科技大学 1.东凌经济管理学院，北京 100083； 2.钢铁生产制造执行系统技术教育部工程研究中心，北京 100083

出版日期:2014-02-28 发布日期:2014-03-14
作者简介:许绍云（1984-），女，山东省人，博士研究生，主要研究方向为先进制造管理、生产计划与调度等.
基金资助:
教育部博士学科点专项科研基金资助项目(20100006110006)；中央高校基本科研业务费专项资金资助项目(FRF-SD-12-011B，FRF-SD-12-012B)；国家自然科学基金资助项目(70771008)

Order Acceptance Based on Lot-spliting Strategy in No-wait Flow Shop

1.Dongling School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China；2.Engineering Research Center of MES Technology for Iron and Steel Production, Ministry of Education, Beijing 100083, China

Online:2014-02-28 Published:2014-03-14

摘要/Abstract

摘要： 在无等待流水车间环境下，考虑订单分批量加工策略的订单接受问题，建立问题的数学模型。由于问题的NP难特性，提出改进的遗传算法对模型进行求解。改进的算法采用正向和反向NEH算法与随机方法产生初始种群，在算法更新过程中将禁忌搜索算法嵌入到遗传算法中来实现局部搜索，避免算法陷入局部最优。最后，算例表明批量划分策略能够有效减少订单的完成时间，实现订单总收益的最大化。通过算法对比，说明了改进遗传算法具有较好的求解效果。

关键词: 订单接受, 无等待流水车间, 批量划分, 改进遗传算法

Abstract: An integer programming model is constructed for the order acceptance problem with lotspliting in nowait flow shop. With the NPhard nature for the problem, an improved genetic algorithm (IGA) is proposed to solve the model. Unlike the standard GA algorithm, based on the basic NEH algorithm, the modified NEH algorithm, and stochastic method, the IGA presents an efficient initialization scheme to construct the initial population. In addition, tabu search for generating neighboring solution is embedded in the IGA to avoid a local optimum. Numerical results indicate the efficiency of lotsplitting in shortening the completion time of orders, which contributes to minimizing order tardiness. Compared with traditional genetic algorithm, the proposed approach yields significant improvement in solution quality.

Key words: order acceptance, no-wait flow shop, lot-splitting, improved genetic algorithm

许绍云1,2，李铁克1,2，王柏琳1,2，王雷1,2. 基于批量划分的无等待流水车间订单接受问题研究[J]. 工业工程, 2014, 17(1): 44-49.

Xu Shao-yun1,2, Li Tie-ke 1,2, Wang Bai lin 1,2, Wang Lei 1,2. Order Acceptance Based on Lot-spliting Strategy in No-wait Flow Shop[J]. Industrial Engineering Journal , 2014, 17(1): 44-49.

参考文献

［1］-Hall N G, Mafazine M J. Maximizing the value of a space mission［J］. European Journal of Operational Research,1994,78(2): 224-241. ［2］Keskinocak P, Ravi R, Tayur S. Scheduling and reliable lead time quotation for orders with availability intervals and lead time sensitive revenues［J］. Management Science, 2001, 47(1): 264-279. ［3］Duenyas L. Single facility due date setting with multiple customer classes［J］. Management Science, 1995,41(3):608-619. ［4］Spearman M L, Zhang R Q. Optimal lead time policies［J］. Management Science, 1999, 45(1): 290-295. ［5］Lewis H F, Slotnick S A. Multiperiod job selection: planning work loads to maximize profit［J］. Computers and Operations Research, 2002, 29(8): 1081-1098. ［6］Slotnick S A, MortonT E. Order acceptance with weighted tardiness［J］. Computers & Operations Research, 2007, 34(10): 3029-3042. ［7］Rom W O, Slotnick S A. Order acceptance using genetic algorithms［J］.Computers & Operations Research, 2009, 36(6): 1758-1767. ［8］Ghosh J B. Job selection in a heavily loaded shop［J］. Computers & Operations Research, 1997, 24(2): 141-145. ［9］Roundy R, Chen D, Chen P, et al. Capacitydriven acceptance of customer orders for a multistage batch manufacturing system: models and algorithms［J］. IIE Transactions, 2005, 37(12): 1093-1105. ［10］-肖依永, 常文兵, 张人千. 多生产线且多节点环境下的订单选择模型［J］. 工业工程与管理, 2008,13 (6): 26-31. -Xiao Yi-yong, Chang Wenbing, Zhang Ren-qian. A research on order acceptance of multiline and multistage［J］. Industrial Engineering and Management, 2008,13 (6): 26-31. ［11］Chang J H, Chiu H N. A comprehensive review of lot streaming［J］. International Journal of Production Research, 2005, 43(8): 1515-1536. ［12］Bukchin J, Masin M. Multiobjective lot splitting for a single product mmachine flowshop line［J］. IIE Transactions, 2004, 36(2): 191-202. ［13］Huang R H. Multiobjective jobshop scheduling with lotspliting production［J］. International Journal of Production Economics, 2010, 124(1): 206-213. ［14］Engin O, Ceran G, Yilmaz M K. An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems［J］. Applied Soft Computing, 2011, 11(3): 3056-3065. ［15］刘琼, 张超勇, 饶运清,等. 改进遗传算法解决柔性作业车间调度问题［J］. 工业工程与管理, 2009, 14(2): 59-66. -Liu Qiong, Zhang Chaoyong, Rao Yunqing, et al. Flexible jobshop scheduling problem with improved genetic algorithm［J］. Industrial Engineering and Management, 2009, 14(2): 59-66.

[1]	陈志新, 董瑞雪, 郝宇楠. 基于改进遗传算法的自动拣选系统拣选位分配建模与优化[J]. 工业工程, 2019, 22(6): 40-44,56.
[2]	罗孝羚, 蒋阳升. 中小城市公交线网及发车频率同步优化[J]. 工业工程, 2017, 20(4): 25-30.
[3]	范佳静. 多资源车间调度问题的研究[J]. 工业工程, 2017, 20(2): 44-50.
[4]	陈建国, 舒辉, 余平祥. 随机返工及重加工情形下的Job-Shop调度问题[J]. 工业工程, 2015, 18(5): 127-133.
[5]	陈淑玲1,2，李铁克1,2，王柏琳1,2. 考虑加班因素的订单接受问题优化模型与算法[J]. 工业工程, 2015, 18(2): 1-08.
[6]	雷涛1，屈挺1，2，聂笃宪1,3，黄国全1,2. 产能约束下的多级装配供应链优化配置方法研究[J]. 工业工程, 2014, 17(5): 93-98.
[7]	聂笃宪1,2，屈挺1,3，陈新1，雷涛1，黄国全1,3. 面向多源采购的多级供应链优化配置方法[J]. 工业工程, 2014, 17(4): 54-62.
[8]	朱伟, 徐克林, 周娜, 李艳冰. 单源多路径配装-运输集成模型算法研究[J]. 工业工程, 2011, 14(2): 66-69.