时间可控的生产调度模型与优化算法研究

发布时间：2022-02-18 07:35

　　对任务安排、服务提供和零件加工等过程进行排序优化的调度理论,在管理决策领域存在着大量的应用,能产生巨大的社会经济效益。经典调度理论中总是假设工件参数是固定不变的,而且机器在整个调度周期内的运行状态也不会发生改变。但管理决策者目前面临的复杂生产过程和客户多样化的需求,使得调度优化问题的研究对象也相应的发生变化。工件的时间参量可以发生改变,机器运行也可能需要中断一段时间来进行诸如保养维护、工具更换、效率调整等活动。而此时工件/机器参数往往是可控的,针对这一新的变化,本文主要研究含可控时间参量的生产调度问题及相应的优化算法。首先,本文研究了带资源依赖的释放时间的单机调度问题。每一工件一旦释放即开始进行加工,其释放时间与假定的初始释放时间存在偏差即会产生释放成本。需要确定工件序列和所有工件的释放时间,使得释放成本、时间表长和总完工时间的加权和总成本目标函数最小。考虑了两种情形:情形一是初始释放时间是限制性的,它是NP难问题;另一情形是初始释放时间为非限制性的,它是多项式时间可解问题,时间复杂度为O（n log n）。其次,基于实际应用中出现的涉及可控且可变加工时间的调度问题,本文研究了含资源依... 

【文章来源】：东南大学江苏省211工程院校985工程院校教育部直属院校

【文章页数】：148 页

【学位级别】：博士

【部分图文】：

图１．１：论文框架结构??１６??

释放时间ｂ的资源消费函数为??ｆ（ｒｊ）?＝?ａ?ｍａｘ｛ｗ?—?ｒｊ，?０｝?＋?＾?ｍａｘ｛ｒｊ?—?ｔ；，?０｝，??其中ａ、／３分别为工件提前和延后释放的单位成本。资源消费函数／＆）是如图２．１（ｂ）所??示的Ｖ－型。而大部分涉及带资源依赖的释放时间的文献中，释放时间的资源消费函数是??ｆ（ｒｊ）?＝?ｏ－ｍａｘ｛ｖ?－?Ｔｊ－，０｝，??其形状如图２．１（ａ）所示。??／（＾）｜??ｍ；?ａｖ??０?ｖ?ｒｊ?〇?ｖ?ｒｊ??（ａ）?（ｂ）??图２．１：释放时间的两类资源消费曲线??以向量７Ｔ?＝?｛?Ｊ丨１］；?？?？?？，ＪＷ｝记录工件集Ｊ的一个工件序列，其中Ｊｂ］＝厶表示人是??安排在序列的第ｊ个位置，向量ｒ?＝伏⑴，．．．，７＾｝记工件序列７Ｔ对应的释放时间。假定??ＩＩ为所有可行工件序列的集合，丑为释放时间７■的可行集合。定义总成本Ｚ（７Ｔ，ｒ：）为??ｎ?ｎ?ｎ??Ｚ（ｔｔ；?＝?／（％］）?＋?６?＋?Ｊ２ｐｌ＾?＋?＾?＋?Ｐｈｉ）－??ｉ＝ｉ?ｉ＝ｊ?ｊ＝ｉ??显然，项Ｕ＝１／（ｒｂ．］）是释放成本，ｍａｘｗＷｒｙｊ?＋?Ｅｂ外ｊ｝是时间表长，＾４（７＾＋削）??是总完工时间。我们的目标是找一个最优工件序列ｔｔ＊和它对应的释放时间序列使??得??Ｚ（７ｒ＊，ｒ＊）?＝?ｍｉｎ?Ｚ（７ｒ，ｒ）．??７ｒｅＵ

理：??引理２．１．最优解中工件之间不含空闲时间。??证明．如图２．２所示，当工件之间含有空隙的话，我们可以证明消除该空隙可以减小调度??成本。对于给定的一个可行解（７Ｔ，７〇，其成本为Ｚ（７Ｔ，ｒ）。假定存在某个正整数Ａ：（０?＜?／ｃ?＜?ｎ）??使得?ｒ［＊：ｊ?＋ｐ间?＜?ｒ［ｆｃ＋１］并记该空隙长为?Ａ?＝?ｒ［；；＋１］?—?（ｒ［ｆｃｊ?＋ｐ［＊］）。??下面我们可以通过改变工件序列ｒ中部分工件的实际释放时间，消除工件和??七＋１丨之间的空闲，构造一个新的可行解㈨，其成本为Ｚ（７Ｔ，Ｔ＇），使得Ｚ（７Ｔ，＜?Ｚ（７Ｔ，。??情形Ｉ：?ｒ＜ｒｗ＋糊。??将序列ｔｔ中空闲后ｎ?－?个工件向前移动Ａ个单位，也就是令实际释放时间??Ｔ?一（『［１］?’?？?．?？?’『［ｎ］）?＿?（『［Ｉ］?’?？?？?？，『［Ａ；］?’?—么，．？?？，ｒ问一?Ａ），??１９??


本文编号：3630466