差异工件批调度问题研究与算法设计

《差异工件批调度问题研究与算法设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中国科学技术大学硕士学位论文差异工件批调度问题研究与算法设计姓名：王栓狮申请学位级别：硕士专业：管理科学与工程指导教师：陈华平20080501Fina1Iy'thcdisscrtationsumsupthcovcranwol^s,andgivessomeresearc^Iproposa1softhekeypointsonmcissueint11ecomingstage.KeyWords：Schedu1ing；BatChprocessingMaChines；HeuriSticA1goritAlgoritllmanalysis；AntColonyOptimization；C0mb

2、i彻rtorialOptilnization中国科学技术大学学位论文相关声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。本人授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文在解密后也遵守此规定。绷年多R研日名：JPt第

3、1章绪论调度问题是组合优化领域中的一类重要问题，在柔性制造系统、现代物流、计算机科学等领域有着非常广泛的应用。求解调度问题是困难的，绝大多数调度问题都是NP难的英至是强NP难；但有效的调度系统可以使现代商业领域增加产出、减少周转时间、减少库存，最终减少生产成本、增加利润和客户满意度，所以调度系统性能的好坏对这些行业的高效运作有着垂要的影响。木章首先对调度问题中的概念及符号做了简单描述，然后介绍了木论文研究的具体问题.差异工件批调度问题，以及和关调度问题的研究现状；最后简述了本论文的研究动机、结果和本论文的结构。1・1调度问题概念调度问题是指作业或任务如何占用有限资源的决策过程

4、，其H标是使某一函数最优，而H标函数通常是对加工时间的长短、资源利川率的描述。调度问题是一类重要的组合优化问题。本文研究机器调度问题，是指如何分配工件（作业）在机器上进行加工处理，以使某一目标函数最优。工件（作业）在机器上加工时可能需要满足一定约束条件，如工件的到达时间、工件的加工顺序、工件加工时是否允许抢占、机器对工件加工时间的影响等等。为便于叙述，本文使用通用的三元组符号口I〃1厂来描述调度问题的类型fl】，即从机器、工件和Fl标函数三个要素来描述调度问题。（1）、口域表示机器的数量、类型和环境，主要有：1（singleprocessor）：指只冇一台机器，此类问题成为单

5、机问題。尸（identicalparallelprocessorS,同速机）：指所有的机器都具有相同的速度；Q（unifom1pam1leiprocessors,恒速机）：指机器的速度不同，但每个速度訥曙期数，不依赖于被加工的工件：R（unrelatedparal1e1p眦cssor,变速机）：指机器的速度依赖于被加工的工件；P、Q、R类机器统称为平行机，记机器的数量为坡，则上述三类平行机问题依次表示为砌、H1、砌.F（f1owshop机器模型，流水作业）：指工件需要在所有机器上加工，且毎个工件在所有机器上的加工序列相同；,（j0bSh0p机器模型，异序作业）:指工件需要在所

6、有机器上加工，且每个工件有自己的加工序列；D（openshop机器模型，口由作业）：指作业需要在所有机器上加工，而每个工件在所有机器上的加工序列可以任意；记机器的数量为H1,则上述三类车间调度问题依次表示为砌、J渤、劝mt何柔性车间调度，相关定义见文献【1】。（2）、〃域表示工件的性质、加工耍求和对加工的限制等约束条件，它可同时包含多项，也可为空，如rf、Pmtn>Pmu分别表示工件有到达时间、工件加工时允许中断、车间调度中工件按排列方式加工。加权^TW1WW/macs；最大延迂护芽工件批调度问题1.2.〔经典调度问题与现代调度问题调度问题有经典调度（classicalsch

7、eduling）和现代调度（modemsch分。根堪史叱i等1993年的观点【2】，经典调度问题有如下四个基本假设：（1）资源的类型：一台机器在任何时刻最多只能加工一个工件，一个工件在任何时刻最多只能被一台机器加工;（2）确定性：调度问题的一个实例所需的任何输人参数都是事先知道的、完全确定的i（3）可运算性：经典调度是在可以运算的程度上研究调度问题，而不去顾及诸如如何确定工件的交货期、如何购置机器和设备等技术上可能发生的问题；（4）单口标和正则性：经典调度假设调度的□标是使衡量排法好坏的一个一维目标函数