Integrated Problem for Lot Sizing and Flexible Flow Shop Scheduling Problem in the Tobacco Industry Considering Setup times and Cigarette Quality

doi:10.12005/orms.2019.0237

Abstract

Abstract: Based on theintegrated problem for lot sizing and flexible flow shop scheduling problem in the tobacco industry, it is formulated as a mixed integer linear model to optimize the lot sizing and scheduling problem whose objective consists of four parts:the production time, the setup times, thecigarette quality and inventory cost. Given the problem is NP-hard, a genetic algorithm is designed to solve this problem based on monolithic method, the infeasible solutions are reduced through the design of genetic operator. Numerical examplesare conducted based on the operation data of a cigarette corporation. The result shows great advantage on decreasing setup times over the previous scheduling plan, which proves the feasibility and validity of our model and algorithm. The effectiveness of the algorithm can be well verified inscheduling decision support for the production of cigarette of real company.

Key words: capacitated lot sizing problem, flexible flow shop scheduling, GA, setup times

摘要： 针对卷烟企业生产中的批量计划和柔性流水车间调度集成问题,构建了整数规划模型,目标函数由卷烟生产时间、生产线调整次数、卷烟质量、库存成本四部分组成。鉴于该问题的NP-hard性,设计遗传算法进行求解,通过合理设计遗传算子,避免不可行解出现。应用某卷烟企业数据得到优化排产结果,与该企业之前依照经验排产方案进行对比,发现优化排程结果在减少品牌转换次数,提高生产的连续性方面具有明显优势。该算法已作为某卷烟企业排产人员的排产参考,应用于排产决策中,取得了良好的效果,对卷烟企业制定排产计划具有一定的实际指导意义。

关键词: 能力约束批量计划, 柔性流水车间调度, 遗传算法, 最大完工时间, 最小化调整次数

CLC Number:

C935

CHAI Jian-bin, LIUHe, BEI Xiao-qiang. Integrated Problem for Lot Sizing and Flexible Flow Shop Scheduling Problem in the Tobacco Industry Considering Setup times and Cigarette Quality[J]. Operations Research and Management Science, 2019, 28(10): 165-174.

柴剑彬, 刘赫, 贝晓强. 考虑机器调整次数和产品质量的卷烟批量计划和柔性流水车间调度集成问题[J]. 运筹与管理, 2019, 28(10): 165-174.

References

[1] 林慧苹,范玉顺,吴澄.基于分层调度模型的生产计划和调度集成研究[J].计算机集成制造系统,2002,8(8):602-606.
[2] Karimi B, Ghomi S M T F, Wilson J M. The capacitated lot sizing problem: a review of models and algorithms[J]. Omega, 2003, 31(5): 365-378.
[3] 韩毅,唐加福,牟立峰,潘震东.粒子群算法求解无能力约束生产批量计划问题[J].管理科学学报,2008,11(5):33-40.
[4] Bitran G R, Yanasse H H. Computational complexity of the capacitated lot size problem[J]. Management Science, 1982, 28(10): 1174-1186.
[5] Graves S C. A review of production scheduling[J]. Operations Research, 1981, 29(4): 646-675.
[6] Luh G C, Chueh C H. A multi-modal immune algorithm for the job-shop scheduling problem[J]. Information Sciences, 2009, 179(10): 1516-1532.
[7] 李琳,霍佳震.钢管生产计划中的多目标柔性Job-shop调度问题[J].系统工程理论与实践,2009,29(8):117-126.
[8] 宋莉波,徐学军,孙延明,查靓.一种求解柔性工作车间调度问题的混合遗传算法[J].管理科学学报,2010,13(11):49-54.
[9] Zhang R, Wu C. A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardinessobjective[J]. Computers & Operations Research, 2011, 38(5): 854-867.
[10] Nguyen S, Zhang M, Johnston M, Tan K C. A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem[J]. Evolutionary Computation, IEEE Transactions on, 2013, 17(5): 621-39.
[11] Nguyen S, Zhang M, Johnston M, Tan K. C. Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming[J]. Evolutionary Computation, IEEE Transactions on, 2014, 18(2): 193-208.
[12] 黄学文,马雪丽,曹德弼.工序顺序柔性的作业车间调度问题的改进遗传算法求解[J].运筹与管理,2013,22(1):65-70.
[13] 宋继伟,唐加福.基于DPSO的无等待混合流水车间调度方法[J].系统仿真学报,2010(10):2257-2261.
[14] Jolai F, Asefi H, Rabiee M, Ramezani P. Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem[J]. Scientia Iranica, 2013, 20(3): 861-872.
[15] 张其亮,陈永生.基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J].系统工程理论与实践,2014(3):802-809.
[16] Rabiee M, Rad R S, Mazinani M, Shafaei R. An intelligent hybrid meta-heuristic for solving a case of no-wait two-stage flexible flow shop scheduling problem with unrelated parallel machines[J]. The International Journal of Advanced Manufacturing Technology, 2014, 71(5-8): 1229-1245.
[17] Karthikeyan S, Asokan P, Nickolas S, Page T. A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems[J]. International Journal of Bio-Inspired Computation, 2015, 7(6): 386-401.
[18] Huang R H, Yang C L, Liu S C. No-wait flexible flow shop scheduling with due windows[J]. Mathematical Problems in Engineering, 2015, 2015. 1-9.
[19] Ramezani P, Rabiee M, Jolai F. No-wait flexible flowshop with uniform parallel machines and sequence-dependent setup time: a hybrid meta-heuristic approach[J]. Journal of Intelligent Manufacturing, 2015, 26(4): 731-744.
[20] 周泓,谭小卫.一种两层生产计划问题建模及其遗传算法设计[J].系统仿真学报,2007,19(16):3643-3649.
[21] Maravelias C T, Sung C. Integration of production planning and scheduling: overview, challenges and opportunities[J]. Computers & Chemical Engineering, 2009, 33(12): 1919-1930.
[22] Meyr H. Simultaneous lotsizing and scheduling on parallel machines[J]. European Journal of Operational Research, 2002, 139(2): 277-292.
[23] 安玉伟,严洪森.一类两阶段生产系统生产计划与调度的集成优化[J].计算机集成制造系统,2012,18(4):796-806.
[24] Ramezanian R, Saidi-Mehrabad M, Teimoury E. A mathematical model for integrating lot-sizing and scheduling problem in capacitated flow shop environments[J]. The International Journal of Advanced Manufacturing Technology, 2013. 1-15.
[25] Wolosewicz C, Dauzère-Pérès S, Aggoune R. A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem[J]. European Journal of Operational Research, 2015, 244(1): 3-12.
[26] Nicholls M G. An integer programming approach to short-term production scheduling in a tobacco plant[J]. Journal of the Operational Research Society, 1998. 1117-1129.
[27] Pattloch M, Schmidt G, Kovalyov M Y. Heuristic algorithms for lotsize scheduling with application in the tobacco industry[J]. Computers & industrial engineering, 2001, 39(3): 235-253.
[28] 王爱民,丁雷,宁汝新,李京生.烟草卷包作业动态调度技术[J].计算机集成制造系统,2010,16(3):603-610.
[29] 徐屹秦,张盛山,吕希胜.基于规则的烟草计划与排产系统[J].计算机系统应用,2013(7):72-76.
[30] 金剑,金钊,祁跃东.卷烟生产计划排产模型建立与优化[J].计算机工程与应用,2013,49(18):253-259.
[31] Gupta J N D. Two-stage, hybrid flowshop scheduling problem[J]. Journal of the Operational Research Society, 1988, 39(4): 359-364.
[32] 唐国春.现代排序论[M].上海科学普及出版社,2003.
[33] 徐玖平.多目标决策的理论与方法[M].清华大学出版社,2005.
[34] Gen M, Cheng R. Genetic algorithms and engineering optimization[M]. John Wiley & Sons, 2000.
[35] 杨红红,吴智铭,王晓骞.基于遗传算法的约束生产批量计划[J].系统工程,2001,19(6):39-44.
[36] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems Man & Cybernetics, 1994, 24(4): 656-667.
[37] 张铁男,韩兵,于渤.生产能力约束条件下的柔性作业车间调度优化[J].系统工程理论与实践,2011,31(3):505-511.