产能不平衡问题的优化模型与算法

发布时间：2017-08-17 01:14

本文关键词：产能不平衡问题的优化模型与算法

【摘要】：在激烈的市场竞争环境中,增加产品种类虽然会让制造商拥有更强的生存能力,但却并不意味着利润的增加。制造商在市场上的成功都明显地受益于复杂的管理,否则可能会对整体收益造成负面的影响。这使得升级用户个性化定制服务成为一个新的商业前沿,对各种个性化需求进行处理的智能系统也成为增强竞争力的关键之一。以往的学者大多关注如何适度生产和调节市场计划,但始终没有出现一个对过程和表现均有决定性影响的策略。客户导向生产配置的深化,产品的多样化将会不断地给生产车间带来动态变化的瓶颈问题和平衡产能问题。本文将所有这类问题称为广义上的“不平衡产能利用”问题,主要研究如何将客户需求转化为内部弹性和提升生产过程的效率问题。本项研究是在应对网络情报系统造成的困难下完成的,解决问题的关键是减少造成需求复杂性的原因,并减少在多工位的生产线环境下的订货生产中,由于偏向于批量在线客户需求而产生的制造过程中的变异。“不平衡产能利用”问题可以分为两个子问题：动态资源瓶颈问题和平衡产能问题。本文目标是探求问题的特征和实质,提出解决问题的算法和模型。本文主要研究内容和创新点可以归纳如下： 1)由于处理此问题的关键难点在于将外部变量转化为内部变量,本文的思路是通过减少投产要素的不一致性(需求波动),对接收订单和拒绝订单的时机进行权衡,以此来平滑生产计划。解决问题的模型由初始化的订单接受模型和初始化的生产线调度模型整合而成,进而利用产能不足和产能过剩的权衡机制加以强化,达到降低不必要产能耗损、收益最大化的目的。产能不足和产能过剩的权衡机制加以强化,达到降低不必要产能耗损、收益最大化的目的。为了测试模型的效果,本文利用耦合限制算法进行计算机模拟实验,研究数据来自一家真实的泰国雨伞企业,结果显示,该模型确实可以降低生产成本,减弱产出的变动幅度。 2)针对动态资源瓶颈问题,构建数学模型。目标是处理瓶颈的转换以达到总利润最大化和产能最小化。根据问题和模型的特点,分别采用了四种排列导向的分布式估计算法来权衡利润和未充分利用的产能,四种分布式估计算法采用了同步的选择和排序规则。之前的研究者大多采用遗传算法(GA算法),将分布式估计算法应用于此类问题本文尚属首次。将两项功能目标整合成一项功能目标有助于降低问题的复杂度。计算机模拟实验的数据也证明了在多条生产线、多个动态瓶颈的环境下,该模型确实可以减少不必要产能并提升总利润。对于本文讨论的问题,基于节点的算法要远优于基于边缘的算法,特别是将其应用于渐进式学习时,效果比遗传算法更好。 3)对于平衡产能问题,本文将加班条件考虑进实验中来,使产能的成本随时间变化而变化。这样动态资源瓶颈问题就转化为三个优化目标：总利润最大化,不必要产能最小化以及获取产能成本最小化。根据问题和应用模型的特点,本文采用了两种基于节点的分布式估计算法。这样,将三项功能目标整合成一项目标,进一步降低了问题的复杂度。较之于只能找到正常工作时间段的最优订单组合的其他算法,引入了惩罚机制的NB-COIN算法,可以找到加班时间段获益最大的订单组合。总而言之,本文的成果不仅要追求产品的高利润,同时也追求生产线的产能协调。在产能不足的情况下,可以通过加班的方式增加生产线的产能、接受更多的订单以提高客户满意度。但加班也会导致生产成本的增加,因此对于多产品、多工位的生产线,需要调整工位产能不足与产能过剩的关系,实现生产线的整体再平衡。本文采用修改/调节四种分布式估计算法—EHBSA,NHBS,COIN以及NB-CO——实现模型的优化求解。实验数据表明,NB-COIN算法具有最好的求解效果,产能均衡目标不仅可以保证生产线产能平衡,同时可以有效提高订单接受的利润。
【关键词】：动态瓶颈 平衡产能 分布估计算法 负面增量学习
【学位授予单位】：北京科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：F273;F224
【目录】：

Acknowledgement5-6
摘要6-8
Abstract8-16
1 Introduction16-27
1.1 Research Background16-17
1.2 Challenge of Research17-19
1.3 Research Main Work19-20
1.4 Structure of Dissertation20-25
1.5 Research Innovation25-27
2 Literlature Review27-55
2.1 Imbalance Of Capacity Utilization Problem27-36
2.1.1 Capacity Strategy31-32
2.1.2 Due Date Management Strategy32-34
2.1.3 Production Strategy34-36
2.2 Research On Bottleneck Problem36-38
2.2.1 Optimization Objectives in Dynamic Bottleneck Problem Research36-37
2.2.2 Solution Approach and Algorithm In Dynamic Bottleneck Problem37-38
2.2.3 Gap In Dynamic Bottleneck Research38
2.3 Research on Assembly Line Balancing38-43
2.3.1 Optimization Objectives in Assembly Line Balancing Research40-41
2.3.2 Solution Approach in Assembly Line Balancing Problem41-43
2.3.3 Gap In Assembly Line Balancing Research43
2.4 Research on Order Acceptance43-49
2.4.1 Optimization Objectives in Order Acceptance Research44-46
2.4.2 Solution approach and algorithm in order acceptanceproblem46-47
2.4.3 Gap in previous order acceptance research47-49
2.5 Research on Order Rejection49-51
2.5.1 Optimization Objectives in Order Rejection Research49
2.5.2 Solution Approach and Algorithm in Order Rejection Problem49-50
2.5.3 Research Gap in Order Rejection Research50-51
2.6 Algorithms for Simultaneously Selection and Sequencing Problem51-55
2.6.1 Introduction to Estimation of Distribution Algorithms52
2.6.2 Estimation of Distribution Algorithms for Permutation-Based Optimization Problem52-55
3 Characteristic of Imbalance of Capacity Utilization Problem and ProblemAnalysis55-73
3.1 Imbalance of Capacity Utilization Problem Characteristic55-59
3.2 Imbalance of Capacity Utilization Problem Problem Analysis59-67
3.2.1 Empirical Data for Problem Analysis59-60
3.2.2 Methodology of Problem Analysis60-62
3.2.3 Result of Problem Analysis62-67
3.3 Discussion of Problem Analysis67-68
3.4 Recommendation Strategy for Solving Imbalance of Capacity Utilization Problem68-71
3.5 Difficulty of Recommendation Strategy71-73
4 Mathematical Model for Imbalance of Capacity Utilization Problem73-80
4.1 Origin And Structure of Model73-74
4.2 Problem Description and Constraint74-76
4.3 Limitations of Model76-77
4.4 Mathematical Model for Imbalance of Capacity Utilization Problem77-80
5 Two Static Bottleneck Resources Problem80-89
5.1 Problem Characteristic80-81
5.1.1 Problem Description80
5.1.2 Mathematical Model for Bottleneck Problem80-81
5.2 Methodology81-83
5.3 Data Generating83-85
5.4 Result85-89
6 Permutation Oriented Estimation of Distribution Algorithms and Applicationson Imbalance of Capacity Utilization Problem89-124
6.1 Permutation Oriented Estimation of Distribution Algorithms89-103
6.1.1 Characteristic of edge histogram based sampling algorithm89-90
6.1.2 Characteristic of node histogram based sampling algorithm90-91
6.1.3 Characteristic of coincidence algorithm91
6.1.4 Characteristic of node based coincidence algorithm91-92
6.1.5 Unification of four algorithms92-103
6.2 Algorithms Comparison and Hypothesis103-106
6.2.1 Ad Hoc learning and incremental learning104
6.2.2 Node based algorithm and edge based algorithm104-105
6.2.3 Positive learning approach and negative learning approach105
6.2.4 Algorithms' hypothesis105-106
6.3 Experimental Parameters Setting106-108
6.4 Experiment Design108
6.5 Data Generating108-110
6.6 Methodology110-113
6.7 Dynamic Bottleneck Problem113-116
6.7.1 Mathematical model for dynamic bottleneck problem113-115
6.7.2 Result115-116
6.8 Capacity Balancing Problem116-124
6.8.1 Mathematical Model for Capacity Balancing Problem116-118
6.8.2 Results118-124
7 Summary,Limitation and Future Direction124-128
7.1 Summary124-125
7.2 Limitation and Future Direction125-128
Reference128-138
作者简历及在学研究成果138-142
学位论文数据集142