加工时间随开工时间线性递减的排序问题.pdf

沈阳师范大学
硕士学位论文
加工时间随开工时间线性递减的排序问题
姓名:李俊杰
申请学位级别:硕士
专业:运筹学与控制论
指导教师:赵传立
20080414
加工时间随开工时间线性递减的排序问题摘要排序问题是一类具有广泛实际背景的组合最优化问题,广泛应用于管理科学,计算机科学和工程技术等众多领域。随着现代工业的发展,经典的排序模型不断被突破。经典排序中通常假设,工件的加工时间是固定不变的常量,而且工件只能在机器上顺次逐个加工。然而在实际问题中,有的工件的加工时间随其开工时间变化而变化,而且有些工件可以作为一批一起加工,因此对这类排序模型的研究具有重要的意义。本文主要研究工件加工时间随开工时间线性变化的平行机排序问题及串行工件同时加工排序问题。首先介绍了排序问题的定义、分类及表示方法,以及工件加工时间依赖开工时间的排序问题和串行工件同时加工排序问题的研究现状。然后分别对工件加工时间随开工时间线性递减的平行机排序问题和串行工件同时加工排序问题进行了讨论。第二章主要讨论了两个具有两台处理机的排序问题:一是平行机排序问题,另一个是每批恰为后个工件的串行工件同时加工排序的平行机排序问题。在这两个问题中,工件加工时间均为开工时间的线性递减函数,目标函数均为极小化总完工时间。对于第一个问题,证明了其最优排序可由工件按基本加工时间不减排列得到,由此得出其最优算法,并指出了该结论对于相应的加工时间随开工时间线性递增的情况不成立。对于第二个问题,根据其与第一个问题在某些性质上的相似性,给出了其最优算法。最后指出本章所讨论的两个问题的结论均可推广到川台处理机的情况。第三章讨论了一些工件加工时间随开工时间线性递减的串行工件同时加工排序问题。分别就单机和流水作业的情况给予了讨论。对于单机排序问题,讨论了目标函数为极小化最大完工时间、总完工时间、最大延误等问题的最优排序的性质,同时就这些性质对相应的加工时间随开工时间线性递增的情况成立与否给予了讨论。对于流水作业排序问题,主要考虑了两种特殊情况。讨论了每批恰为七个工件、极小化最大完工时间问题的最优算法。论文最后对本文的内容作了总结,并提出了未来工作的努力方向。关键词:排序,串行工件同时加工排序,线性递减
③綾鹊鴆¨¨誥谢鷜ぁ辥胋蚢鄑妇谢、,鲫尽韉,赳瑆鱒⒌辀证鷊琧廿騦弱嬲碰妇,、篒甌9阯,辀,耫鏽簕ⅱ鬳猟邪也阉.∞琤嬲瞖甴‘她⒑糳,Ⅸ’,他.ⅱ鬳.,騦唾.Ⅱ瑆蔡餿Ⅱ鎥冶琣ⅱ鬿
総衷襬雡鷈锄躶埘咖璐缸恤コ鷇畇:璐佃μ飉蒾疘,,、析瞖緀也舱瞖也読嗳鏽,瞐甀:¨,—¨
垒刍釜:丕。丝星:支:墨学位论文独创性声明学位论文使用授权声明日期:婴呈:茎:墨垒互笙:垒。除文中已经注明引用的内容外,本论文不包含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体,均已在文中作了本人授权沈阳师范大学研究生处,将本人硕士学位论文的全部或部分内容编入有关数据库进行检索;有权保留学位论文并向国家主管部门或其采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文本人所呈交的学位论文是在导师的指导下取得的研究成果。据我所知,明确说明并表示了谢意。作者签名:日期:指定机构送交论文的电子版和纸质版,允许论文被查阅和借阅;有权可以在解密后适用本规定。
第一章引言一、排序问题的定义和分类排序论又称时间表理论,是运筹学的一个分支,是组合最优化学科的一个重要组成部分,广泛应用于管理科学,计算机科学和工程技术等众多领域。排序问题是工业生产中一类带有普遍性的问题,将原材料通过各种机器加工成所需要的零件需要排序;将生产出来的许多零件组装成某种产品需要排序;一个大型的工程在兴建当中,必须对各类人员进行安排,对各种器材的供应进行调度,都需要排序。这类问题,何时何地都可以看到。对于大型的、复杂的工作,排序的好坏对工程费用的大小影响很大。这使得排序问题具有深刻的实际背景和广阔的应用对于排序问题,不同的模型需要不同的方法去处理。有时,只要将模型的条件稍加变化,原算法就将不再适用,这也是排序问题的一大特点,同时也使得排序问题模型繁多。随着现代工业的发展,经典的排序模型已经被突破,新的模型层出不穷,因此排序理论可分为经典排序和新型排序P滦团判蚴窍喽杂诰典排序而言,即非经典的排序。新型排序的特征是突破了经典排序关于资源类型、确定性、可运算性、单目标和正则性等基本假设,主要包括可控排序、成组分批排序、在线排序、同时加工排序、准时排序和窗时排序、不同时开工排序、资源受限排序、随机排序、模糊排序、多目标排序等。近些年来,从实际背景中提出的许多新的排序模型,使得排