资源描述：
《n个零件在m台机床上的加工顺序问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、拿第,期年月中司种科学技术成就个零件在台机床上的加工顺序问题越民义韩继业中国科学院数学研究所摘要,。,在工厂的零件加工车间设有个零件要在台机床上加工各零件根据工艺上,,的要求按一定顺序通过这些机床如何安排这些零件顺序使预先给定的指标达到最优,这就是运筹学中所谓的排序问题本文所考虑的排序问题假设各零件皆依同一顺序通过这些机床劝每个零件的加工时间为已知每个机床在同一时间只能加工一个零件目的是要寻求一个,顺序使总的加工时间为最短我们所得到的主要结果如下。,了为从功经,设为一川的某一排列交换相邻两数字和的位置后
2、的,田、‘。,排列和分别表示在和斌之下总加工时间则当、,,。‘“,,,,“·,,八蕊悦砚“,。。‘时有簇我们所给出的条件比所给出的条件要弱从推广,斗法则这一角度看本文定理的结果已足最好的结果,,本文所讨论的问题属于排序问题这一问题根据数学处理方法的不同实际上包含很多。问题本文所讨论的是个零件在台机床上的加工问题每个零件都是先在第一台机床上,,⋯,,加工然后再送到第二台机床上加工⋯最后送到第台机床上加工且零件在各机床上的加工顺序一致同顺序每台机床在同一时间只能加工一种零件每个零件在每台机床上,,加工的时间
3、为已知且不受偶然事件例如机床发生故障等的干扰只要机床有空就可对零,,,件进行加工即不存在存放地点等问题在这些条件下我们要求事先将这个零件安排一个一,,顺序使得从最先一个零件在第一台机床上开始加工起到最后个零件在第台机床上加工,完毕止这段时间为最短即寻求一最优方案,,一最先研究了这一问题他曾对两台机床的情况给出了个简便的算,法本文定理其后这一间题就引起了不少人的注意但他们所用的方法主要是分支定一,与普一界法这种方法从某种意义上来说乃是一种穷举法它通的一,列举方法不同之处在于在列举过程中可以根据已进行的计算
4、结果排除一些明显的不必要本文年月日收到、,第期越民义韩继业个零件在‘台机床上的加工顺序问题的“”,,计算当和相当大时即使利用高速计算机这类方法也是不可行的于是就希望能找,,,到一些条件若这些条件得到满足则某些方案一定比另外某方案好因而事先就可排除一些,,,不需要考虑的情况最近得到了一个判定相邻两个零件先后的条件但他给出的条件是相当复杂的一、可行线与可行和,,,,,。,。,儿,,人记零件在机床、设有台机床⋯和个零件⋯上的。,。’。。,,。,,二,。,,加工时间为当零件的加工顺序⋯给定时其中叭表示,,。,。
5、,,⋯的一种排列我们可将排成矩阵“一““,「夕又田”“,。·口少一二,,介⋯,,,、,。邓田,多卜’面我们给出关于。的可行线与可行和的概念。。。,召,切。,定义将矩阵中与用一条折线连接起来此折线只能向右水平延伸或间,。解。下垂直延伸其顶点只能是这种折线我们称之为对应于的一可行线全体可行线所成之集即田一是,。,,。,,,。,飞,,“,,,,,田,,二,⋯⋯,“、,,,,,,,。。阴。。成钱蕊镇夕一乍⋯⋯。,,‘定义设为一可行线则称艺叹为对应于。的可行和交,‘。,可行线与可行和的概念之所以有用在于它与机床加
6、工零件的起止时间有如下关系。,,。,,,,,,引理设叭。为一加工顺序如每个零件都须依次通过且⋯⋯,二,,诸零件在各机床上的加工顺序一致则从开始加工零件几起到加工完零件几为止了,。这段时间之长。等于矩阵的所有可行和中的最大数八。艺,叱正〔。,证先证的情况因矩阵只有两行故显然有二一一·黑爹,艺一走七、馨客。,。口,,,,。当时总加工时间是故式成立假设式对成立现要证咬式对,。十。,,也成立不难看出零件几在上经历的过程只有两种在上不需等待而亿即被加工图此时有,的空闲时间科学多田,“,田,’了,,,。。⋯一艺。,
7、,⋯,。。,。,,⋯,。。,,,·,,。,故,·田,。田,、,一一一刁、产、、、。⋯一⋯卜馨乙汁必︸、少。。,在上需等待图此时有图。,,,。,工,,。。。,了。。⋯⋯。,⋯,。艺。,田,,,故亦有式根据归纳法的假设即得。,,。,一。。,,,⋯。、,导宝‘。了,“,“‘“,‘·山个‘了‘招、自了与夕、,故当时引理得证。再对做归纳法假设式对,成立记几在机床上的加工完毕时刻为入立,,,一几一,,,有⋯若我们把视为一零件在上的加工时间且它在。,,。上的加工时间为耐娜则和可视为两台机床的情况因而有。,,⋯,。,一
8、干夕。,。、呢暇”仁不‘二,由归纳法的假设有,。,,‘艺,害交〔了,。。。,、,其中是连接和的一可行线将上式代入约式即得·,,。,艺间。口,胜⋯艺州田,《了《”互,〔沙。“,。,,,,,,,,因连接和的任一可行线都可表成。。,。的形式故式即为。台机床时的式引理证完、二二时的最优工序安排,一。,,。,根据上节的引理我们可把工序安排问题表示为寻求心产⋯才使得,。艺,〔左,,。一,、由于全部工序的个数是个故最优工序一定存在对于的情况给出了最,优工
