文档介绍：曲阜师范大学
硕士学位论文
带配送时间的在线分批调度问题
姓名:王成飞
申请学位级别:硕士
专业:数学、运筹学与控制论
指导教师:张玉忠
20080401
们考虑的两个问题的竞争比均为万,其中艿:掣;并首次提出了独立配送模型下的带配送时间的在线分批调度问题最大完工时间,这类问题也是吠瓯傅模颐嵌酝嗷那樾胃隽私扑惴≦摘要.,并且证明了它们的竞争比分别不超过其中口屯其中关键词分批排序:在线排序:竞争比:近似算法:配送时间曲阜师范大学硕士学位论文排序问题是一类重要的组合优化问题,它被广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域,,有着重要的应用背景,:第一章主要介绍了排序问题产生的背景,计算复杂性理论,分批排序,:分批加工、独立配送模型以及分批加工、;首次提出了一种新的配送模型:按批配送模型,<』ぜ石,蔿·
万..,..曲阜师范大学硕士学位论文.,瑃.,琲瓸—琩,—。,瑆
颇ǎ詈,吾鄏甒:,曲阜师范大学硕士学位论文籄甀..—;;
作者签名:王或飞作者签名:王威名日期:训、·曲阜师范大学硕士学位论文原创性说明曲阜师范大学硕士学位论文使用授权书日期:矽们畉坯本人郑重声明:此处所提交的硕士论文《带配送时间的在线分批调度问题》,是本人在导师指导下,在曲阜师范大学攻读硕士学位期间独立进行研究工作所取得的成果。论文中除注明部分外不包含他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的个人和集体,均已在文中己明确的方式注明。本声明的法律结果将完全由本人承担。《带配送时间的在线分批调度问题》系本人在曲阜师范大学攻读硕士学位期间,在导师指导下完成的硕士学位论文。本论文的研究成果归曲阜师范大学所有,本论文的研究内容不得以其他单位的名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定,同意学校保留并向有关部门送交论文的复印件和电子版本,允许论文被查阅和借阅。本人授权曲阜师范大学,可以采用影印或其他复制手段保存论文,可以公开发表论文的全部或部分内容。导师曲阜师范大学硕士学位论文.
第一章绪言琍—琣,,叫§排序问题的概念与符号本章简单介绍了排序问题的由来及应用背景,概述了排序问题的相关定义,记号及排序问题是一类重要的组合最优化问题,,如任务的到达时间、完工的限定时间、,国际上通用的是忍岢龅娜问硎痉ǎ桓排序及配送问题基本上由处理机氖俊⒐ぜ肪臣澳勘旰呃纯袒只有一个处理机的排序问题称为单处理机排序问题,,如果所有的处理机都具有相同的功能,:如果所有的处理机都具有相同的速度,称之为同速机:如果处理机的速度不同,但每个处理机的速度都是常数,不依赖被加工的任务,称它们恒速机:如果处理机的速度依赖被加工的任务,,本文中工件基本的约束或性质有以下几类:简称工时话阌胮,表示,指工件,,■表示,指的是工件.,,,表示,指工件,,的运输时间:∥薰氐氖焙蛞话阌胑表示采用第衷耸浞绞剿枰5姆延茫勘旰本文涉及到的目标为极小化最大完工时间和总配送时间,除此之外,目标函数还有总完工时间、加权总完工时间等例如,本文所研究的排序问题用三参数表示如下:—,猙,琯珺曲阜师范大学硕士学位论文
篒—,Α躳§计算复杂性节的和,,┮恍┯幸娴钠舴ⅲ解这类问题有