考虑生产计划的多周期切割问题优化研究

doi:10.12005/orms.2018.0225

运筹与管理 ›› 2018, Vol. 27 ›› Issue (10): 17-22.DOI: 10.12005/orms.2018.0225

考虑生产计划的多周期切割问题优化研究

马宁^1,2, 周支立^1,2, 刘雅^1,2

1.西安交通大学管理学院工业工程系,陕西西安 710049;
2.西安交通大学机械制造系统工程国家重点实验室,陕西西安 710049

收稿日期:2015-09-20 出版日期:2018-10-25
作者简介:马宁(1990-),男,河南人,博士研究生,研究方向:优化调度;周支立(1960-),男,浙江人,教授,博士,研究方向:物流管理;刘雅(1982-),女,河北人,副教授,博士,研究方向:物流与生产调度。
基金资助:
国家自然科学基金项目(71390333,71301127);陕西省自然科学基金项目(2015JM7369)

Research on the Multi-period Cutting Stock Problem Coordinating with Production Planning

MA Ning^1,2, ZHOU Zhi-li^1,2, LIU Ya^1,2

1.Department of Industrial Engineering, School of Management, Xi’an Jiaotong University, Xi’an 710049, China;
2.State Key Laboratory for Manufacturing Systems Engineering, Xi’an Jiaotong University, Xi’an 710049, China

Received:2015-09-20 Online:2018-10-25

摘要/Abstract

摘要： 切割生产广泛存在于工业企业,是原材料加工的重要环节。已有文献主要关注单周期切割问题,但是切割计划也是生产计划的一部分,切割计划和生产计划应该协调优化,达到全局最优。本文研究考虑生产计划的多周期切割问题,目标是最小化运营成本,包括准备成本、切割成本、库存成本以及母材消耗成本。首先建立混合整数规划模型;提出动态规划启发式算法;最后对算例在多种情境下测试,分析成本因子变化对最优结果的影响。算法结果与CPLEX最优结果比较,平均误差为1.85%,表明算法是有效的。

关键词: 切割问题, 协调调度, 动态规划, 启发式算法

Abstract: Cutting stock production is the key stage of raw materials processing, which widely spreads in industrial companies. There is much literature concentrating on single period cutting stock problem. However, cutting stage is part of production plan. An advanced manufacturing plan consists of not only cutting plans but also multi-period production plans. This paper investigates a multi-period cutting stock problem coordinating with production planning. The objective is minimizing total operational cost, including production setup cost, cutting patterns change cost, inventory cost and input rods consumed cost. We first formulate a mixed integer mathematical model, and propose a dynamic based heuristic programming to solve it. Finally we test random instances based on different scenarios, analyzing the effect of cost factor. The average cost is 1.85%, compared with optimal solutions obtained by CPLEX. This indicates the algorithm can obtain near-optimal solutions efficiently.

Key words: utting stock, coordinating scheduling, dynamic programming, heuristic

中图分类号:

F272.2

马宁, 周支立, 刘雅. 考虑生产计划的多周期切割问题优化研究[J]. 运筹与管理, 2018, 27(10): 17-22.

MA Ning, ZHOU Zhi-li, LIU Ya. Research on the Multi-period Cutting Stock Problem Coordinating with Production Planning[J]. Operations Research and Management Science, 2018, 27(10): 17-22.

参考文献

[1]Haessler P W. Controlling cutting pattern changes in one-dimensional trim problems[J]. Operations Research, 1975, 23(3): 483-493.
[2]Yanasse H H, Limeira M S. A hybrid heuristic to reduce the number of different patterns in cutting stock problems[J]. COMPUTERS & OPERATIONS RESEARCH, 2006, 33(9): 2744-2756.
[3]Lodi A, Martello S, Monaci M. Two-dimensional packing problems: a survey[J]. European Journal of Operational Research, 2002, 141(2): 241-252.
[4]Karimi B, Fatemi Ghomi S M T, Wilson J M. The capacitated lot sizing problem: a review of models and algorithms[J]. Omega, 2003, 31(5): 365-378.
[5]Liu Y, Chu C B, Wu F. A heuristic for variable size multiobjective two-dimensional bin packing[J]. International Journal of Production Research, 2014, 52(12): 3450-3465.
[6]Liu Y, Chu C B, Wang K L. A dynamic programming-based heuristic for the variable sized two-dimensional bin packing problem[J]. International Journal of Production Research. 2011, 49(13): 3815-3831.
[7]Liu Y, Chu C B, Yu Y G. Aggregated State Dynamic Programming for a Multiobjective Two-dimensional bin Packing Problem[J]. International Journal of Production Research. 2012, 50(15): 4316-4325.
[8]靳鹏,马华伟,杨善林.考虑订购成本的多目标一维下料优化模型[J].系统工程学报,2013,28(1):19-27.
[9]Hendry L C, Fok K K, Shek K W. A cutting stock and scheduling problem in the copper industry[J]. Journal of the Operational Research Society, 1996, 47(1): 38-47.
[10]Nonås S L, Thorstenson A. A combined cutting-stock and lot-sizing problem[J]. European Journal of Operational Research, 2000, 120(2): 327-342.
[11]Nonås S L, Thorstenson A. Solving a combined cutting-stock and lot-sizing problem with a column generating procedure[J]. Computers & Operations Research, 2008, 35(10): 3371-3392.
[12]Gramani M C N, Fran A P M. The combined cutting stock and lot-sizing problem in industrial processes[J]. European Journal of Operational Research, 2006, 174(1): 509-521.
[13]Poltroniere S C, Poldi K C, Bragion Toledo F M, et al. A coupling cutting stock-lot sizing problem in the paper industry[J]. Annals of Operations Research, 2008, 157(1): 91-104.
[14]靳鹏.配料企业下料与调度协调优化模型研究[D].合肥工业大学,2013.
[15]Mcdiarmid C. Pattern minimisation in cutting stock problems[J]. Discrete Applied Mathematics, 1999, 98(1-2): 121-130.
[16]Pisinger D. A minimal algorithm for the 0-1 knapsack problem[J]. Operations Research. 1997, 45(5): 758-767.

考虑生产计划的多周期切割问题优化研究

Research on the Multi-period Cutting Stock Problem Coordinating with Production Planning

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	马咏, 何正文, 江波, 王能民. 一种求解柔性资源约束前摄性项目调度问题的启发式算法[J]. 运筹与管理, 2021, 30(8): 14-20.
[2]	庞南生, 叶博童. 项目鲁棒调度的资源分配启发式算法研究[J]. 运筹与管理, 2021, 30(8): 21-27.
[3]	胡修武, 徐悦, 王秀利. 呼叫中心坐席人员排班问题优化模型与算法研究[J]. 运筹与管理, 2021, 30(8): 44-51.
[4]	陈伟, 张玉林. “仓店一体化”模式下订单拣选与配送集成调度优化[J]. 运筹与管理, 2021, 30(7): 16-22.
[5]	王磊, 柏庆国, 任建峰. 具有两种运输方式选择的物流排序问题[J]. 运筹与管理, 2021, 30(6): 1-5.
[6]	董纪阳, 何万里. 集中通勤接送服务的最小化成本模型及算法[J]. 运筹与管理, 2021, 30(12): 28-34.
[7]	刘磊. 航空公司中的飞行员配置研究[J]. 运筹与管理, 2021, 30(10): 1-5.
[8]	滕尚儒, 何成铭, 丛彬. 装备维修器材生产路径双目标问题优化决策方法研究[J]. 运筹与管理, 2020, 29(6): 1-9.
[9]	梁峰, 徐苹. 基于MDP和动态规划的医疗检查预约调度优化方法研究[J]. 运筹与管理, 2020, 29(5): 17-25.
[10]	张文思, 李金林, 冉伦, 王伟. 随机服务时间下异质患者门诊预约调度优化[J]. 运筹与管理, 2020, 29(5): 26-36.
[11]	焦小刚, 郑斐峰, 徐寅峰, 刘明. 考虑泊位疏浚的连续型泊位和动态岸桥联合调度[J]. 运筹与管理, 2020, 29(2): 47-57.
[12]	边展, 张倩, 徐奇, 靳志宏. 带时间窗取送货问题的混合算法[J]. 运筹与管理, 2020, 29(2): 99-115.
[13]	井彩霞, 吴瑞强, 贾兆红. 并行分批排序综述[J]. 运筹与管理, 2020, 29(1): 223-239.
[14]	陈刚, 付江月, 何美玲. 考虑居民选择行为的应急避难场所选址问题研究[J]. 运筹与管理, 2019, 28(9): 6-14.
[15]	曹萍, 张剑, 熊焰. 具有质量差异的项目支付进度问题研究——以软件项目为例[J]. 运筹与管理, 2019, 28(9): 192-199.