工件可选择的平行机在线排序

论文摘要

平行机排序是应用非常广泛的一类排序模型。本文主要研究的是一类平行机在线排序问题，并且工件是可以选择的。用三参数法表示我们的模型即是：Pm|on-line，rj，D|∑fj．其中D指机器的使用期限，fj为工件Jj的加工利润，目标函数是使得在机器的使用期限内所获得的总利润最大。我们在本文所讨论的模型是一种新模型：一种背包问题（knapsack problem）的在线排序形式。在现有文献中还未见有此类模型的研究工作。在本文中所谓的在线，是指工件集是按时（over-time）到达的，工件的所有性质（包括到达时间）在它到来之前都是未知的，工件在到来之前不能被安排加工。平行机是指模型中的机器环境，指m台类型相同、速度相同的机器同时投入作业。由于我们所讨论的模型目标函数值为求最大，故我们所用的竞争比ρ定义为，其中对任意一个实例A，σ为算法得到的排序，π为离线最优序。显然这里的ρ满足0≤ρ≤1。本文模型的最显著特点是：工件具有可选择性并且必须即时加工。所谓可选择性，是指在工件到达之时，决策者可以接受加工而获得利润，也可以拒绝加工而失掉利润，即到来的工件并非都要安排加工，可以选择抛弃其中的某些工件。所谓即时加工，是指工件不允许等待加工，每一个到达的工件或者被选择在它的到达时刻开始加工，或者被抛弃掉，不存在某一个被选择的工件的开工时间大于它的到达时间。这种模型在现实生活中有着很广泛的应用，例如公司或企业投资一批相同类型的机器进行生产活动，定单的到来时间及内容事先是不知道的，且决策者可以接受定单也可以拒绝定单。由于市场竞争激烈，接受的定单必须立刻开工，而拒绝的定单很可能立刻被别的企业接手，故被拒绝的定单以后也不可再接手加工。此模型的离线情形中当取rj=0（j=1，…，n）且允许工件在到达时间之后加工时，它即是一个背包问题。因而可以证明该模型的离线情形（工件在到达时刻立即加工或抛弃）是NP-困难问题。而对于本模型中工件的利润fj与加工时间pj不相关的情形，问题会比较困难。故在本论文中我们主要讨论该模型中一些较为特殊的情形：工件的利润fj与加工时间pj呈线性关系。本文的内容主要分两大部分：第一章，我们主要给出了排序论的介绍、一些用到的基本概念、排序的记号以及模型的介绍等。第二章中，我们首先在第一节中给出了该模型中fj=1情形的所有在线算法竞争比的上界1／2，fj=pj的一般情形（工件加工时间任意）不具有竞争比为常数阶的在线算法，进而可知模型中fj与pj呈线性关系fj=μj+λjpj（μj，λj＞0）的一般情形也不具有竞争比为常数阶的在线算法。然后在第二节里，给出了fj=1且工件序列只包含两类工件情形（小工件加工时间为1，大工件加工时间为d）的在线算法。包括：只有两台机器，大工件加工时间d≥2时，找到了一个竞争比为1／2的在线算法A1，且此算法为最具竞争性的；当有任意m台平行机时，找到了一个在线算法A2，证明了对于m=2k（m为偶数），d≥k+1的模型此算法的竞争比为1／2，且为最有竞争性的；对于m=2k+1（m为奇数），d≥2k+2的模型，此算法的竞争比为k／（2k+1），为渐近意义下最优的。最后在第三节中，对于fj=pj，工件的加工时间只有两种（小工件加工时间为1，大工件加工时间为d），有任意m台平行机的情形，找到了一个在线算法A3同样证明了对于m=2k（m为偶数），d≥k+1的模型此算法的竞争比为1／2，且为最有竞争性的；对于m=2k+1（m为奇数），d≥2k+2的模型，此算法的竞争比为k／（2k+1），为渐近意义下最优的。

论文目录

• 摘要
• Abstract
• 第一章 概述
• §1.1 排序论介绍
• §1.2 基本概念
• §1.3 排序的记号
• §1.4 模型特点和主要结果
• 第二章 工件可选择的平行机在线排序
• §2.1 竞争比的上界
• j=1情形的在线算法'>§2.2 两类工件且f_j=1情形的在线算法
• j=p_j情形的在线算法'>§2.3 两类工件且f_j=p_j情形的在线算法
• 后记
• 参考文献
• 致谢