已阅读5页,还剩61页未读, 继续免费阅读
(系统工程专业论文)钢铁工业中无委托板坯匹配问题的模型与优化算法研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
东北大学硕士学位论文 摘要 钢铁工业中无委托板坯匹配问题的模型与优化算法研究 摘要 本文针对钢铁企业中经常遇到的无委托板坯匹配问题进行了深入的研究。无 委托板坯匹配问题是在给定个板坯集合和一个合同集合的情况下,如何确定在 满足生产工艺实际约束下,将板坯分配给合适的合同,以保证生产管理目标的优 化。研究该问题能够提高无委托板坯的材料利用率、提高合同的完整性及交货期 满足率要求、减少后工序无委材发生量,从而最终降低成本,提高企业的竞争力。 无委托板坯匹配问题的复杂性主要体现在在确定合理的匹配方案时需要考虑 的实际因素包括:钢级、维数( 长度、宽度) 、重量( 重量、极限重量) ;合同的完整 性要求:无委托板坯与合同匹配时以优充次的情况。实际约束包括:一个板坯在 符合匹配条件时只能分配给一个合同:分配给每一个合同的板坯总重量尽量不超 过合同欠量。问题的目标是:1 ) 尽可能多地将无委托板坯匹配给合适的合同;2 1 尽 量将紧急的板坯和紧急的合同优先匹配上:3 ) 尽可能地将欠量少的合同先完成。 上述复杂的实际因素和约束的考虑,以及多个冲突目标的要求都额外地增加了问 题的建模与求解的难度。 根据无委托板坯匹配问题的特点,考虑上述的实际因素和约束及目标要求, 建立了一个整数规划数学模型。该数学模型与广义指派问题( g e n e r a l i z e d a s s i g n m e n tp r o b l e m ) 数学模型既相似又有差别。相似点在于两个问题都是要求将对 象( 板坯、客户) 找到一种关系( 匹配、指派) 。不同点在于广义指派问题要求所有的 客户必须都被指派,而无委托板坯匹配问题首先要考虑板坯能否匹配,然后将能 匹配的板坯尽可能的匹配给合同,所以板坯允许剩余,但剩余带有惩罚。由于无 委托板匹配数学模型的简单情况可以归结为广义指派问题,而广义指派问题是 n p h a r d 问题,所以无委托板坯匹配问题也是n p h a r d 问题。 由于浚问题是一个大规模组合最优化问题,变量和约束数目众多。通过分析 其可行解的约束和变量之间的关系,应用约束传播技术在不影响解的质量的情况 下有效地降低了问题求解规模。 东北大学硕士学位论文 摘要 拉格朗日松弛算法是一种基于最优化的近似算法,已成功地用于求解多类 n p h a r d 组合最优化问题。它具有较好的方向迭代性,以及算法的自我评价性。本 文针对模型特点,提出两种拉格朗曰松弛算法的求解策略:1 ) 松弛模型中板坯分 配唯一性约束,松弛问题分解为基于合同的背包子问题。对于每一个子问题,应 用动态规划求解;2 ) 松弛模型中合同需求量约束,松弛问题分解为基于板坯的子 问题,应用最负费用枚举策略求解子问题最优解。两种策略乘子的更新均采用次 梯度方法。 上述两种拉格朗同松弛算法的程序用c + + 语言编写,并在p e n t i u mi v 主频 3 0 g h z 的计算机上进行实验仿真。涉及到的实验数据均来自于钢铁企业生产实际。 计算结果表明两种拉格朗日松弛算法对于求解无委托板坯匹配问题都是有效的。 l r l 算法的两个平均对偶间隙指标分别大约为0 2 和0 1 ,平均计算时间大约为 2 5 2 秒;l r 2 算法的两个平均对偶间隙指标分别大约为o 7 7 1 0 5 ,平均计算时 间大约为1 5 秒。l r l 算法能够得到很好的对偶间隙,但是耗时较多。虽然l r 2 算 法比l r l 算法运算时间短,平均对偶间隙却比l r l 效果差。 关键词:无委托板坯匹配问题,最优化,拉格朗日松弛,约束传播技术,动态规 划 查! ! 垄兰壁主兰竺笙查一 垒坐! 竺! s t u d yo nm o d e l l i n ga n da l g o r i t h m sf o rt h eo p e n o r d e rs l a b m a t c h i n gp r o b l e mi ni r o na n ds t e e li n d u s t r y a b s t r a c t t h i sp a p e rg i v e sa ni n - d e p t hr e s e a r c ho nt h eo p e n - o r d e rs l a bm a t c h i n gp r o b l e m w h i c hi sf r e q u e n t l ye n c o u n t e r e di ni r o na n ds t e e lp r o d u c t i o n g i v e nas e to f o r d e r sa n d as e to fo p e n o r d e rs l a b s ,t h ep r o b l e mi st od e t e r m i n ew h i c hs l a b sm a yb ea s s i g n e dt o s u i t a b l eo r d e r ss u b j e c tt op r a c t i c a lm a t c h i n gc o n s t r a i n t sf o ro p t i m i z i n gt h eo b j e c t i v eo f p r o d u c t i o nm a n a g e m e n t r e s e a r c ho nt h i sp r o b l e mc a nn o to n l yi m p r o v et h em a t e r i a l u t i l i z a t i o nr a t eo fo p e n o r d e rs l a b ,t h ei n t e g r a l i t yo fo r d e ra n dt h es a t i s f a c t i o nl e v e lo f d u ed a t e ,b u ta l s od e c r e a s et h ew i pl e v e lo fs u r p l u sm a t e r i a l so ft h ed o w n s t r e a m o p e r a t i o n s t h eo p t i m i z e dt h eo p e n o r d e rs l a bm a t c h i n gp r o b l e mc a nt h e r e f o r e d e c r e a s et h ec o s ta n ds t r e n g t h e nt h ec o m p e t i t i o na b i l i t yo f t h ee n t e r p r i s e s o m ep r a c t i c a lf a c t o r st ob ec o n s i d e r e ds u c ha ss t e e lg r a d e ,d i m e n s i o n ( 1 e n g t h , w i d t h ) ,w e i g h t ( w e i g h t ,w e i g h tl i m i t ) ,r e q u i r e m e n tf o ro r d e ri n t e g r a l i t y , a n dt h ec a s et h a t t h eo p e n o r d e rs l a b 、i t l lh i g h e rs t e e lg r a d ei sa s s i g n e dt ot h eo r d e rw i t hl o w e rs t e e l g r a d ew i l l e x t r aa d dd i f f i c u l t n e s st ot h eo p e n o r d e rs l a bm a t c h i n gp r o b l e m t h e p r a c t i c a lc o n s t r a i n t so ft h ep r o b l e mu n d e rc o n s i d e r a t i o na r ea sf o l l o w s :al e g a ls l a bc a n b er e m a i n e di na nu n a s s i g n e ds t a t ei nf e a s i b l es o l u t i o n ;t h et o t a lw e i g h to ft h es l a b s a l l o c a t e dt oa no r d e rc a l ln o te x c e e dt h ed e m a n do ft h a to r d e r i t so b j e c t i v ei st om a t c h a sm a n yo p e n - o r d e rs l a b sa sp o s s i b l et os u i t a b l eo r d e r s ,t om a t c ht h eu r g e n ts l a bt ot h e u r g e n to r d e rp r e f e r e n t i a l l ya n dt os a r i s f yt h es m a l l v o l u m eo r d e rd e m a n da ss o o na s p o s s i b l e t h ec o m p l i c a t e dp r a c t i c a lf a c t o r sa n dc o n s t r a i n t st o g e t h e rw i t hm u l t i c o n f l i c t i n go b j e c t i v e sc o n s i d e r e da b o v em a k et h em o d e l i n ga n ds o l v i n go ft h ep r o b l e m m o r ed i f f i c u l t c o n s i d e r i n gt h ea b o v ep r a c t i c a lp r o d u c t i o nc o n s t r a i n t s ,a ni n t e g e rp r o g r a m m i n g m o d e li sp r o p o s e db a s e do nt h ec h a r a c t e r so ft h eo p e n o r d e rs l a bm a t c h i n gp r o b l e m t h em o d e li ss i m i l a rt oo n e so ft h eg e n e r a l i z e da s s i g n m e n tp r o b l e mb u tt h e r ea r es o m e - l v 东北大学硕士学位论文 a b s t r a c t d i f f e r e n c e sb e t w e e nt h e s et w op r o b l e m s w h i c hn e e d st of i n dar e l a t i o n ( m a t c h i n g , t h et w op r o l e m sh a v eac o m m o nf e a t u r e a s s i g n m e n t ) o f t h eo b j e c t s ( s l a b ,c u s t o m e r ) t h ed i f f e r e n c e sl i et h a tt h e g e n e r a l i z e da s s i g n m e n tp r o b l e mr e q u i r et h a ta l l t h e c u s t o m e r sm u s tb ea s s i g n e do u tc o m p l e t e l y , b u tf o rt h eo p e n o r d e rs l a bm a t c h i n g p r o b l e m t h es l a b sa 托p e r m i t t e dt ob el e f tu n m a t c h e dw i t hp e n a l t i e s t h eo p e n o r d e r s l a bm a t c h i n gp r o b l e mi sn p , h a r dp r o b l e ms i n c ei t ss i m p l i f i e dc a s ec a nb er e d u c e dt o t h eg e n e r a l i z e da s s i g n m e n tp r o b l e m ,w h i e hi saw e l l k n o w nn p h a r dp r o b l e m , i ti sal a r g e - - s c a l ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mw i t hm a n yv a r i a b l e sa n d c o n s t r a i n t s b ya n a l y z i n g t h er e l a t i o n s h i pb e t w e e nc o n s t r a i n t sa n dv a r i a b l e s , c o n s t r a i n tp r o p a g a t i o nt e c h n i q u eh a sb e e na d o p t e dt oc u tt h ef e a s i b l er e g i o nw i t h o u t d e s t r o y i n gt h es o l u t i o nq u a l i t y , l a g r a n g i a nr e l a x a t i o n ,a sac l a s s i c a lo p t i m i z a t i o n b a s e da p p r o x i m a t i o na l g o r i t h m , h a sb e e n s u c c e s s f u l l ya p p l i e dt o s o l v em a n yk i n d so fc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m sb e c a u s ei th a st h ea d v a n t a g e so fb o t ht h ea b i l i t yo ns e l f - e v a l u a t i o no fs o l u t i o n q u a l i t ya n dt h el o g i ci ns e a r c h i n ga l o n gas p e c i f i e dd i r e c t i o nd u r i n ga l li t e r a t i v ep r o c e s s t h i sp a p e rp r o p o s e st w ol a g r a n g i a nr e l a x a t i o na l g o r i t h m s f i r s t ,b yr e l a x i n gt h e a s s i g n m e n t t y p ec o n s t r a i n t so fs l a bm a t c h i n gi nt h em o d e l ,t h er e l a x e dp r o b l e ma r e d e c o m p o s e di n t ot h em u l t i p l ei n d e p e n d e n ts u b p r o b t e m se a c ho fw h i c hi sk n a p s a c k p r o b l e mc o r r e s p o r d i n gt o ao r d e rw h i c hc a nb es o l v e db yd y n a m i cp r o g r a m m i n g s e c o n d ,t h er e l a x e dp r o b l e mo b t a i n e db yr e l a x i n gt h eo r d e r - d e m a n dc o n s t r a i n t si nt h e m o d e li sa l s od e c o m p o s e di n t ot h es l a b - l e v e ls u b p r o b l e m se a c ho fw h i c hi ss o l v e d o p t i m a l l yb ye n u m e r a t i o nm e t h o df i n d i n gt h em o s tn e g a t i v ec o s t t h em u l t i p l i e r s r e l a t e dt ot h et w oa l g o r i t h m sa r eu p d a t e db ys a m es u b g r a d i e n t o p t i m i z a t i o n t h ep r o p o s e dt w o l a g r a n g i a nr e l a x a t i o na l g o r i t h m sa r ed e v e l o p e db yu s i n gc + + l a n g u a g e ,a n de x p e r i m e n t sa r ei sc o r r i e do u to np e n t i u m i v3 0 一g h zp cw i t h1g b r a m a l lt h ee x p e r i m e n td a t aa r ec o l l e c t e df r o mt h ep r a c t i c a lp r o d u c t i o ni na ni r o n a n ds t e e le n t e r p r i s e t h ec o m p u t a t i o n a lr e s u l t ss h o wt h a t l a g r a n g i a nr e l a x a t i o n a l g o r i t h mi se f f e c t i v ef o rs o l v i n gt h eo p e n - o r d e rs l a bm a t c h i n gp r o b l e m t h et w o a v e r a g ed u a lg a p so fl r la l g o r i t h m sa r ea b o u to 2 a n do 1 r e s p e c t i v e l y ,a n dt h e a v e r a g ec o m p u t a t i o nt i m ei sa b o u t2 5 0 s a l s o ,t h et w oa v e r a g ed u a lg a p so fl r 2 a l g o r i t h m sa r ea b o u to 7 a n do 5 ,a n dt h ea v e r a g ec o m p u t a t i o nt i m ei sa b o u t15 s v 东北大学硕士学位论文a b s t r a c t l r la l g o r i t h mc o m p a r e dw i t l ll r 2c a r lg e tab e t t e rd u a lg a p b u tc o n s u m em o r et i m e k e y w o r d s :t h eo p e n - o r d e rs l a bm a t c h i n gp r o b l e m ,o p t i m a z t i o n ,l a g r a n g i a nr e l a x a t i o n , c o n s t r a i n tp r o p a g a t i o n ,d y n a m i cp r o g r a m m i n g v i - 独创声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加 以标注和致谢的地方外,不包含其他人已经发表或撰写过的研究成果,也不包括本人为 获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名 签字日期 绮勇玖 少f 2 ,瑶 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定:即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借 阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交 流。 ( 如作者和导师同意网上交流,请在下方签名:否则视为不同意) 学位论文作者签名: 导师签名 签字日期: 签字日期: 查! ! 垄兰堡主兰堡垒查 苎二主堕堕 第一章绪论 本章首先介绍了无委托板坯匹配问题的来源、研究目的、背景和意义。对无 委托板坯匹配问题研究现状进行了简单的介绍。最后总结了本文的工作。 1 1 问题的研究目的及意义 1 i 1 问题的来源及研究目的 在现阶段,钢铁工业是国民经济的支柱产业,为国民经济其它重要行业( 如机 械、建筑、汽车制造) 提供原料,在国民经济的发展中发挥着重要的和基础性的作 用。随着全球经济一体化和高新技术的迅猛发展,钢铁企业面临着同益激烈的竞 争,而且竞争规则发生了改变。降低生产成本、提高产品质量、提高服务水平、 快速响应市场、应对竞争规则的改变已成为钢铁企业应对市场变化的重要手段。 现如今,由于国际钢材市场不景气,造成钢材价格下跌,且对国内钢铁企业产生 很大压力,国内钢铁企业如何面对这种压力关系到企业的生存与发展,因此如何 降低生产成本、提高企业效益是目前钢铁企业面对的一个重要研究课题。 无委托板坯匹配问题是钢铁企业中经常遇到的问题,同时也属于钢铁企业物 流学的范畴。物流学萌芽于第二次世界大战末期,当时美国军事部门运用运筹学 和电子计算机技术有效地改善了部队的后勤供应工作,这些技术成果后来被应用 于生产与流通领域逐步形成了现代物流科学。在近二十年中,这门年轻的综合应 用学科有了相当快的发展,在一些发达国家,已获得可观的经济效益与管理效益。 物流技术被誉为继改进工艺、提高劳动生产率之后的“企业第三个利润源泉”。 在本文中,研究一个重要的钢铁企业经常遇到的问题一无委托板坯匹配问 题。问题是这样定义的:给定组合同订单以及一些无委托板坯,然后在满足实 际生产约束的情况下决定哪些板坯配给合适的合同。基于问题的特点,该问题是 大规模组合最优化问题。 1 1 2 问题的背景、特点及意义 组合最优化是在离散的、有限的数学结构上,寻找一个满足给定约束条件并 使其目标函数值达到最大或最小的解。它是解决离散问题的优化问题,是运筹学 的一个重要分支,通过数学方法的研究实现离散事件的最优编排、分组、次序或 东北大学硕士学位论文 第一章绪论 筛选等。许多实际问题,特别是来自生产作业与物流管理中的那些实际问题,都 与这种组合最优化问题有关,如背包问题、旅行商问题、装箱问题、定价问题、 占线问题、物流配送( 运输、选址、仓储) 等。如今,求解组合最优化问题遍及许多 学科领域,如计算机科学、应用数学、管理科学等其它相关学科,而且,随着求 解问题的算法研究和实现算法的技术提高,一些新的组合最优化问题不断出现, 求解方法也得到快速发展。 组合最优化问题分为两类:一类为“容易”问题,这类问题数量较少,且能 在多项式的时间内求解;另一类则是“困难”问题,这类问题占绝大多数,对于 这类问题来讲。所有已知的算法在最坏情况都需要指数计算时间,然而,其中也 有一些“相对较容易的困难”问题,如背包问题,若问题的数据中某些数有界则 该问题存在伪多项式算法,它需要多项式时间。因此,组合最优化的理论研究的 中心内容是解决问题,包括改进算法,研究问题之间、算法之间及问题与算法之 间的各种关系。由于多数组合最优化问题是n p h a r d ,而且不同问题有不同的组合 结构,所以研究求解这些问题的近似算法成为一个挑战性的研究方向。 求解组合最优化问题的数学方法有两类;一类为精确算法,如分支定界、动 态规划、线性规划等:一类为近似算法,它又可分为基于最优化的近似算法和基 于智能优化的近似算法,前者包括拉格朗日松弛、列生成和状态空间松弛等,而 后者包括启发式算法、模拟退火、遗传算法、蚁群算法、禁忌搜索和神经元网络 等。虽然基于智能优化的近似算法易于实现且速度较快,但是它不能保证求得全 局最优解;而利用精确算法像分支定界和动态规划求解n p h a r d 问题时即使能得 到最优解,但所需要的计算时间过长,这对实际问题并不可行。因此人们希望找 到一种有效算法使得它能在合理的时间内提供具有可量化指标的近优解。在2 0 世 纪7 0 年代,出现一种有助于计算的思想,即发现许多困难问题可看作是容易问题 被相对少量的一组边约束复杂化。将这些边约束对偶化则产生一个易于求解的拉 格朗日问题,它的最优值是原问题最优值的下界( 最小化问题) ,因此拉格朗只问题 可用于代替线性规划松弛以提供分支定界算法中的界。这种算法已经成功地用于 求解许多组合最优化问题,如生产调度、旅行商和一般的整数规划问题等。 本文中研究的问题正是来自于钢铁企业实际生产中经常遇到的问题。在钢铁 企业中,由于重视产能最大化,忽视了原料的成本,结果浪费了很多能源。如何 使企业物流合理化是一个亟待解决的问题。企业物流合理化涉及多方面的内容, 如各种设备、设施在生产空阃的合理布局,以减少物流量:合理控制库存,以减 少资金占用等。企业物流合理化的基本思路为:通过物流的系统化、现代化,提 东北大学硕士学位论文 第一章绪论 高物流系统的自身素质;通过提高企业战略计划的一体化,改善物流系统的内部 环境;通过流通的社会化、现代化,改善物流系统的外部环境。物流管理包括以 下几个方面: ( 1 ) 供应物流。生产企业、流通企业或消费者购入原材料、零部件或商品的物 流过程称为供应物流。对于生产企业而言,供应物流包括原材料等一切生产资料 的采购、进货运输、仓储、库存管理、用料管理和供料输送。它是企业物流系统 中独立性相对较强的子系统,并且和生产系统、搬运系统、财务系统等企业各部 门以及企业外部的资源市场、运输条件等密切相关。 ( 2 ) 销售物流。生产企业、流通企业售出产品或商品的物流过程称为销售物流。 在钢铁企业中,销售物流是成品出厂装车或装船、运输到用户接收入库为止的物 流过程。该部分物流主要在钢铁企业外部发生,属于直接面向用户的物流,物流 过程是否流畅直接影响到用户对企业的评价。 ( 3 ) 生产物流。从生产企业购入物资入库起,直到产品离开成品库的物流全过 程称为生产物流。在钢铁企业中,从购入的原材料输入高炉炼铁生产区域开始到 产品离开成品库的物流全过程成为钢铁企业生产物流。因此,生产物流和钢铁企 业生产过程密切联系,如生产物流中断,生产过程也就停止了。 ( 4 ) 回收物流。在生产和流通活动中,一些物资可以回收并再加以利用的物流 过程称为回收物流。在钢铁企业中最常见的回收物流为冶金行业每年大约有3 0 万吨废钢铁( 金属废弃物) 作为炼钢原料使用。 ( 5 ) 废弃物流。生产和流通系统中所产生无用废弃物的处理活动中的物流过程 称为废弃物流,如开采矿山时产生的涂石的处理,炼钢过程中产生的钢渣,以及 工业废水、工业垃圾的处理等。 由于生产物流是企业的核心,与企业的发展息息相关。生产物流是指碾材料、 燃料、外购件投入生产后,经过下料、发料、运送到各个加工点和存储点,以在 制品的形态。从一个生产单位( 仓库) 流入另一个生产单位( 仓库) ,按照规定的生产 工艺过程进行加工、储存的全部生产过程。因此,生产物流的形势和规模取决于 生产的类型、规模、方式和生产的专业化与协作化水平。 生产物流区别于其它物流系统的最显著特点是它和企业生产密切联系在一 起。只有合理组织生产物流过程,以有可能使生产过程始终处于最佳状态。如果 物流过程组织的水平低,达不到基本要求,即使生产条件、设备、工艺再好,也 不可能降低生产成本更谈不上取得较好的经济效益。 由于生产物流与企业生产密切相关,所以对生产物流以及相关的理论和实践 东北戈学硕士学位论文 第一章绪论 研究比较多,目前绝大多数有关钢铁企业的研究都集中在生产物流方面,如铁水 调度问题【1 】【2 】 3 】、炼钢一连铸一连轧相关调度问题【4 】1 5 】【6 】f 7 】、板坯倒垛问题【8 】 9 】、板 坯合同匹配问慰川【3 l 【1 4 i i l 5 】等。在日益严峻的竞争形势下加强我国钢铁企业生 产物流优化问题的研究已经成为非常紧迫的课题。但由于生产物流的多样性和复 杂性以及生产工艺和设备的不断更新,如何更好地组织生产物流是物流理论研究 人员和管理人员始终追求的目标。 1 2 本文问题研究特点 1 2 1 无委托板坯匹配问题的研究特点 无委托板坯匹配问题在决策问题上的特征:一个带有板坯欠量的合同订单集 合和一个所能匹配的板坯的集合,根据生产实际情况,确定每个板坯和每个合同 的符合情况,要求在满足合同订单需求的条件下,使板坯尽可能多地匹配给合同, 但是板坯存在优先级,合同也存在优先级,另外还有尽可能的使欠量小的合同达 到匹配完整。综上所述,无委托板坯匹配问题是尽可能多地将优先级高的板坯匹 配给优先级高的合同。 无委托板坯匹配问题是一个多目标问题,由于生产实际约束很多,决定了该 问题是一个更为复杂的问题。但是该问题并不是不可求解的,由于一个无委托板 坯只能匹配给一个合同,而一个合同可以由多个板坯进行匹配。这与广义指派问 题( g e n e r a l i z e da s s i g n m e n tp r o b l e m ,简称g a p ) 类似。 广义指派问题是这样定义的:一个是客户的集合,一个是供应商集合。关于 每一个供应商都有一个能力限制,并且每一个客户只能由一个供应商提供服务。 问题是将最优地将所有客户指派给供应商。在这个问题中,每一个客户都只能由 一个供应商为其提供服务。而无委托板坯匹配问题只要求一个板坯匹配给一个合 适的合同,但是并没有要求这块板坯必须匹配出去,只要求尽可能多地将板坯匹 配出去。这就是广义指派问题与无委托板坯匹配问题最主要的区别。 广义指派问题已经由f i s h e r 等7j 证明是n p h a r d 问题,该问题是应用数学规 划问题中的一个重要分支。具体的实例包括资源调度、通信网络的设计fg r i g o r i a d i s 等t l s l ) 、集中器路出问题( c a m p e l l 和l a n g e v i n :悖1 1 。 现在已经有许多算法被用于求解该问题,c a t t r y s s e 和v a nw a s s e n h o v e t 2 0 j 针对 于该问题的方法作了全面的概述,许多算法都是基于松弛方法、分解技术以及分 支定界策略,到目前为止最快最有效的算法包括r o s s 和s o l a n d 2 ”,m a r t e l l o 和 东北太学硕士学位论文 第一章绪论 研究比较多,目前绝大多数有关钢铁企业的研究都集中在生产物流方面,如铁水 调度问题2 l 3 i 、炼钢一连铸一连轧相关调度问题 4 1 【5 1 咄”、板坯倒垛问题【8 1 【9 1 【j o 、板 坯合同匹配问题m 州聃1 等。在日益严竣的竞争形势下加强我国钢铁企业生 产物流优化问题的研究已经成为非常紧迫的课题。但由于生产物流的多样性和复 杂性以及生产工艺和设各的不断更新,如何更好地组织生产物流是物流理论研究 人员和管理人员始终追求的目标。 1 2 本文问题研究特点 1 2 i 无委托扳坯匹配问题的研究特点 无委托板坯匹配问题在决策问题上的特征:一个带有板坯欠量的合同订单集 合和一个所能匹配的板坯的集合,根据生产实际情况确定每个板坯和每个合同 的符合情况,要求在满足合同订单需求的条件下,使板坯尽可能多地匹配给合同, 但是板坯存在优先级,合同也存在优先级,另外还宵尽可能的使欠量小的合同达 到匹配完整。综上所述,无委托板坯匹配问题是尽可能多地将优先级高的板坯匹 配给优先级高的合同。 无委托板坯匹配问题是一个多目标问题,由于生产实际约束很多,决定了该 问题是一个更为复杂的问题。但是该问题并不是不可求解的,由于一个无委托板 坯只能匹配给一个合同,而一个合同可以由多个板坯进行匹配。这与广义指派问 题( g e n e r a l i z e da s s i g m n e n tp r o b l e m ,简称g a p ) 类似。 广义指派问题是这样定义的:一个是客户的集合,一个是供应商集台。关于 每一个供应商都有一个能力隈制并且每一个客户只能出一个供应商提供服务。 问题是将最优地将所有客户指派给供应商。在这个问题中,每个客户都只能由 一个供应商为其提供服务。而无委托板坯匹配问题只要求一个板坯匹配给一个合 适的合同,但是并没有要求这块板坯必须匹配出去,只要求尽可能多地将扳坯匹 配出去。这就是广义指派问题与无委托板坯匹配问题最主要的区别。 广义指派问题已经由f i s h e r 等 j ”证明是n p h a r d 问题,该问题是应用数学规 划问题中的一个重要分支。具体的实例包括资源凋度、通信网络的设计rc j r i g o r i a d i s 等l ”集中器路由问题c a m p e l l 和l a n g e v i n f ”饥 现在已经有许多算法被用于求解该问题c a t t r y s s e 和v a nw a s s e n h o v e 2 0 】针对 于该问题的方法作了全面的概述,许多算法都是基于松弛方法、分解技术咀及分 支定界策略,到目前为止最快最有效的算法包括r o s s 和s o i a n d 叫m a r t e l l o 和 支定界策略,到目前为止最恢最有效的算法包括r o s s 和s o l a n d 2 ”m a r t e l l o 和 东北戈学硕士学位论文 第一章绪论 研究比较多,目前绝大多数有关钢铁企业的研究都集中在生产物流方面,如铁水 调度问题【1 】【2 】 3 】、炼钢一连铸一连轧相关调度问题【4 】1 5 】【6 】f 7 】、板坯倒垛问题【8 】 9 】、板 坯合同匹配问慰川【3 l 【1 4 i i l 5 】等。在日益严峻的竞争形势下加强我国钢铁企业生 产物流优化问题的研究已经成为非常紧迫的课题。但由于生产物流的多样性和复 杂性以及生产工艺和设备的不断更新,如何更好地组织生产物流是物流理论研究 人员和管理人员始终追求的目标。 1 2 本文问题研究特点 1 2 1 无委托板坯匹配问题的研究特点 无委托板坯匹配问题在决策问题上的特征:一个带有板坯欠量的合同订单集 合和一个所能匹配的板坯的集合,根据生产实际情况,确定每个板坯和每个合同 的符合情况,要求在满足合同订单需求的条件下,使板坯尽可能多地匹配给合同, 但是板坯存在优先级,合同也存在优先级,另外还有尽可能的使欠量小的合同达 到匹配完整。综上所述,无委托板坯匹配问题是尽可能多地将优先级高的板坯匹 配给优先级高的合同。 无委托板坯匹配问题是一个多目标问题,由于生产实际约束很多,决定了该 问题是一个更为复杂的问题。但是该问题并不是不可求解的,由于一个无委托板 坯只能匹配给一个合同,而一个合同可以由多个板坯进行匹配。这与广义指派问 题( g e n e r a l i z e da s s i g n m e n tp r o b l e m ,简称g a p ) 类似。 广义指派问题是这样定义的:一个是客户的集合,一个是供应商集合。关于 每一个供应商都有一个能力限制,并且每一个客户只能由一个供应商提供服务。 问题是将最优地将所有客户指派给供应商。在这个问题中,每一个客户都只能由 一个供应商为其提供服务。而无委托板坯匹配问题只要求一个板坯匹配给一个合 适的合同,但是并没有要求这块板坯必须匹配出去,只要求尽可能多地将板坯匹 配出去。这就是广义指派问题与无委托板坯匹配问题最主要的区别。 广义指派问题已经由f i s h e r 等7j 证明是n p h a r d 问题,该问题是应用数学规 划问题中的一个重要分支。具体的实例包括资源调度、通信网络的设计fg r i g o r i a d i s 等t l s l ) 、集中器路出问题( c a m p e l l 和l a n g e v i n :悖1 1 。 现在已经有许多算法被用于求解该问题,c a t t r y s s e 和v a nw a s s e n h o v e t 2 0 j 针对 于该问题的方法作了全面的概述,许多算法都是基于松弛方法、分解技术以及分 支定界策略,到目前为止最快最有效的算法包括r o s s 和s o l a n d 2 ”,m a r t e l l o 和 东北大学硕士学位论文 第一章绪论 t o t h 22 1 ,f i s h e r 等 1 7 1 ,c a t t r y s s e 等f 2 3 】。 由于无委托板坯匹配问题与广义指派问题有许多相似性。广义指派问题已经 被证明是n p h a r d 问题,所以无委托板坯匹配问题也是n p h a r d 问题。同样解决广 义指派问题的算法也同样能够用于解决无委托板坯匹配问题。 1 2 2 无委托板坯匹配问题的研究现状 无委托板坯匹配问题在钢铁企业普遍存在,所以国内外许多钢铁企业以及科 研机构都对此问题进行过研究,并且取得了很多科研成果,而且有很多都已经应 用于生产实践。其中k a l a g n a n a m 等学者 1 1 】对于该问题的研究非常深入。k a l a g n a n a m 等学者将这个问题归结为双目标的库存匹配问题。一个目标是与剩余库存匹配的 合同订单重量最大,另一个目标是与合同订单匹配上的板坯损耗重量最小。这个 双目标的匹配问题考虑了两类约束,最后建立一个整数规划的数学模型,可以有 很多软件求解。该文章还给出了求解库存匹配问题的个启发式算法,并对于实 际问题,将整数规划和启发式算法求解的性能进行了比较。得出结论:整数规划 方法对于大规模问题无法在6 个小时内得到最优解。启发式算法对于任何问题的运 行时间都不超过几秒钟。这个启发式算法已经在大的钢铁企业应用,估计每年可 节约3 百万美元。 v a s k o 等学者i l2 】针对钢铁企业存在的重要问题即板坯和客户订单的匹配问题 进行了研究。由于问题的离散性特点,作者建立了整数规划模型,通过添加个 虚拟的订单和一个虚拟的板坯把该问题转化为一个运输问题,这就可以通过 b e r t s e k a s 的网络节点方法有效的求解。最后通过启发式,运输问题所求的解就能 转换成实际可行的解。用该方法求解实际的例子,在3 8 6 机器上能够在1 分钟内 得到很好的可行解。 另外对于该问题的研究,许多学者并不局限在板坯匹配合同订单的层面上, 而更多把研究重点放在根掘合同设计板坯的问题上。f r i s c h 等学者分析生产 实际中的约束,提出了关于钢铁企业板坯设计模型,并且十目应地给出符合生产实 际的计算过程。k a l a g n a n a m 等学者针对于这种板坯设计f = 7 题提出一种有效的方 法。这种方法能够降低依据合同订单设计板坯的数目,这种算法是基于启发式算 法,这种算法是针对于集覆盖问题的一种贪婪思想。在k a l a g n a n a m 等学者【1 1 1 的文 章中应用了s a l m a n 等学者1 1 6 j 提出的算法。在s a l m a n 等学者的文章中提到,对 于复杂的晟优化问题,设计一种能够在所有实例中表现出色的启发式算法是非常 困难的,结果很多都是依据具体的问题实例而产生的算法。在这篇文章中,对于 东北大学硕士学位论文 第一章绪论 处理复杂问题的一个变化算法是将几个启发式算法搜集起来,用来共同处理相互 的问题,以使问题得到更好的解。如果分别应用这些启发式并不可能使每个问题 都能得到更好的解,所以这个方法是非常有吸引力的。 1 2 3 求解无委托板坯匹配问题的算法 求解板坯匹配问题的方法很多,在前面已经提到了一些算法。在本文中,将 采用一种最优化算法求解该问题,即拉格朗同松弛算法。 拉格朗日松弛算法是基于最优化算法的一种近似算法,也是求解n p h a r d 问题 的一种有效算法,它是二十世纪七十年代在计算领域最有效的思想之一,是能够 保证许多困难问题可以被看作一些包含比较少的复杂约束集的简单问题。把复杂 的约束对偶化就产生一个容易求解的拉格朗日问题,并且其最优值是原问题的最 优值的一个下界( 对最小化问题来说) 。因此,拉格朗日问题能够被用于代替线性 松弛在分支定界算法中为原问题提过一个界。正如我们所看到的,拉格朗同方法 与线性规划相比有许多重要的优点。 1 9 7 0 年以前,在离散最优化中多次用到过拉格朗日方法,其
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 电子竞技赛事裁判培训与考核指南
- 2026小学教资面试道法答辩高频考题题库
- 初中生物教资面试答辩易错题题库及解析
- 高中英语教资面试试讲高频考题题库
- 企业级数据丢失与恢复工具手册
- 2026事业单位计算机岗面试高频考题试卷及解析
- 索取售后服务评价结果的联系函(4篇)
- 初中英语教资面试答辩题库及参考答案
- 2026事业单位档案岗面试高频考题题库及答案
- 项目进度报告及预算调整通知函4篇
- 肾动脉栓塞介入术
- 《邮轮烹饪英语》-《邮轮烹饪英语》-Appendixes
- 魅力辽宁课件
- 天津市2021-2024年中考满分作文59篇
- 口腔正畸接诊流程技巧
- 军队职工抚恤管理办法
- GB/T 39542.3-2025技术制图活动铅笔第3部分:黑铅芯HB铅芯弯曲强度
- 班级历程回顾
- 《ERP软件实训》教学大纲
- 森林旅游学习通超星期末考试答案章节答案2024年
- 县乡教师选调进城考试-教育法律法规题库含答案(突破训练)
评论
0/150
提交评论