文档介绍：摘要业的从业人员与理论研究者的密切关注。本文主要研究排序问题在供应链管理第一章主要介绍了供应链与排序问题的一些知识和概念,并且总结了近些年来在综合考虑排序与运输的问题研究方面取得的一些成果。台机,所有工件的顾客相同时,我们设计了最坏情况界为是任意正常数慕ソ钣潘惴ā5被骰肪呈橇教ㄆ叫谢泄ぜ墓丝拖嗤保我们给出了了最坏情况界为的近似算法。个工厂可以加工所有属于本身的工件,也可以把一些工件运送到另一个工厂去材料不需要运送,工件完成加工后,需要被运送回有需求的工厂;加工之前,需要先运送原材料,工件完成加工后不需要被送回有需求的工厂;有需求的工厂。问题的目标函数都是极小化最后一个完工工件的完工时间。对这三个问题,我们分别设计了最坏情况界为,和的线性时间近似算订单来加工产品,并把完成的订单交由第三方物流公司运送给顾客。每个订单包含不同的产品数量,而且必须在顾客要求的时问之前送达。订单产生的运输费用与其中的产品数量以及运输需要的时间有关。我们的目标是安排一个加工订单的持序并为每个订单选择运输时间,使得所有订单都能在承诺的最迟到货时间之前到达其顾客处,并且产生的总运输费用尽量地少。我们给出了此问题排序问题是一类经典的组合优化问题,从上世纪年代至今受到了许多行中的应用。众所周知,供应链是由多个环节构成的,因此我们不能孤立地研究排序问题,而要把排序问题与其它过程综合考虑。全文共分四章。第二章研究工件占用运输工具空间不同的综合考虑运输和排序的问题。在这类问题中,工件在机器上完成加工后,需要由唯一的一辆运输工具运送到相应的顾客处。运输工具的空间是有限的,每个工件占用运输工具的空间各不相同。目标函数是极小化最后一个到达顾客的工件的到达时间。当机器环境是单第三章讨论了允许在两个加工工厂之间运送原材料或成品的排序问题。每加工。这样的运送需要一定的时间。若某个工厂需要另一家工厂加工一些工件,根据工厂和工件的不同要求,有以下三种情形:诠ぜ庸ぶ埃诠ぜ诠ぜ庸ぶ埃枰O仍怂驮牧希ぜ瓿杉庸ず螅枰1辉怂突法,并且给出了动态规划算法。第四章研究了带承诺到货时间的排序问题。在该问题中,企业根据顾客的摘要
的最坏情况界为慕扑惴ǎ⑶抑っ髁苏飧鼋缡墙舻摹关键词:排序问题,供应链管理,近似算法,最坏情况界,动态规划。摘要
..,甒,,琽,,.·瑆,.
,,,,.琣猚—甌.,瑆—甀瑃甌瓼—瑆·,,一—
第一章绪论排序问题与供应链管理排序问题是组合优化中一类有着重要理论意义和广泛实际背景的问题,其实质是研究如何在满足一定要求下,对需求完成任务的合理安排在着密切的联系,并广泛应用到生产计划调度,信息处理,物流管理,服务行业等领域。近几十年来,排序问题得到了运筹学、工程学、管理学和计算机科学界的极大关注,并且随着对经典问题研究的日趋深入,大量具有实际背景的序文献发表在国内外的学术期刊上,可以这样说,排序研究已经成为组合优化按照学术界多年来形成的惯例,我们把需要完成的任务称为工件般指在同一时刻,一台机器至多加工一个工件,一个工件也只在一台机器上加/【】,其中:,分别机器环境用来描述机器的数量、不同机器之间的关系等与机器有关的性质。常见的机器系统包括单台机合低持谢饔懈髯圆煌募庸に俣龋合低持谢鞲鞑幌嗤ぜ诓煌魃系募工件特征一般包括工件的加工时间ǔR渤莆9ぜざ,工件的释放以得到某种意义下的最优结果。排序理论与理论计算机科学和离散组合数学存新问题不断涌现。自上世纪年代人们开始研究排序问题至今,已有大量的排领域最活跃的分支之一。把完成任务需要的资源称为机器颐窍M业揭桓隹尚械呐判沟媚掣龈ǖ哪勘旰锏阶钚大U饫锟尚幸工,并且该排序满足问题特定的约束要求。描述一个排序问题可以用一种所谓“三参数表示法甪代表特定的机器环境、工件特征和最优准则。它们是排序问题的三个组成部分。、平行机⒘魉饕⒂行蜃饕妥杂勺饕取F渲校叫谢萜湫阅艿牟煌箍煞治H啵和推叫谢合低持兴谢鞯墓δ堋⑿释耆谎煌类平行机但任意工件在不同机器上的加工时间有相同的比例关系;不同类平行机工时间比不全相同。在三参数表示法中,它们分别用琎,表示。第一章绪论
则为:找一个可行排序,使得工件的最大完工时间%旺在所有的可行排序中取序问题的可行排序中工件以的完工时间,则称%戕,8门判虻墓时间,工件相互之间的依赖关系,工件加工时是否允许中断以及中断恢复后再加工时是否要受惩罚等等。根据排序者对工件信息的了解程度,又可将排序问者在排序开始前就已经知道工件的全部信息,例如工件数、每个工件的加工时即只有在位于某个工件前的全部工件均被安排完毕后,排序者才能知道该工件但在实际问题中,大量的问题是介于两者之间的,即我们或者知道该问题的一些整体信息,或者知道后续工件的部分信息。我们把这样的问题称为是半在线所谓最优准则,通俗地讲,