限选机器上的在线排序问题

摘要

在恒同机中每台机器都有相同的速度，这里我们假设所有机器的速度为1.这样工件的加工时间与机器没有关系，仅与它自身的长度有关.限选机器是指机器因功能不同导致工件在选择机器加工时受到限制，从而工件只能在允许加工的特殊机器子集上加工.将允许加工工件的机器组成的集合称为加工集. 在线排序是指只有在工件到达之后才能知道工件的信息，甚至它的存在性.工件按到达方式可分为按时在线和按序在线两类. 在本文第二章中，我们主要探讨了 m 台限选恒同机上的在线分批排序问题.平行分批是指一台机器一次可以同时加工B 个工件.当 B≥n 时，我们称该分批为无界平行批. 当 B < n 时，我们称它为有界平行批.其中n 表示工件数目. 在这里工件是按时到达的（即当有工件出现时，我们可以选择立即加工或等待)，且所有工件的加工长度都相同.目标函数是最小化所有工件被运输完成的时间. 我们假定有充分多的运输工具.即工件一旦完工便可被运输.对于工件具有嵌套加工集的情形，我们分别讨论了批容量有界和批容量无界两种情况. 其中嵌套的定义为：对任意两个工件Ji 和 Jj的加工集Mi 和 Mj有 Mi?M j或 Mj?Mi或 Mi∩Mj=?.当批容量无界时，可用三参数法表示为P m 丨M j(nested),pj= p，rj,qj,P-batch，B >≥n，online|Lmax.我们给出了竞争比为的 最好可能的在线算法. 当批容量有界时，我们考虑运输时间有如下限制：对任意两个工件Ji 和 Jj的加工集 M i 和 M j ,若 M i ? M j ,则有 qi ≥qj 成立.对 Pm|Mj(nested),pj=p，rj,qj,P-batch，B < n，online|Lmax,我们给出竞争比为的最好可能的在线算法.另外，我们考虑了工件具有分层加工集（即任意两个工件的加工集具有包含与被包含的关系)的情形，即问题 P m丨 M j (GOS),pj=p，rj,qj,P-batch，B < n，online|Lmax. 此处运输时间的限制于第三节中的限制相同.当B ≥2 时，问题的在线算法的竞争比的下界也是f ,上述嵌套情形的算法对该问题亦是最好可能的.当B=1 时，我们证明该问题的下界是3/2,同时给出竞争比为3/2的最好可能的在线算法. 在本文第三章中，我们研宄了 m 台恒同机上工件长度在固定区间内取值的在线排序问题，且工件具有两层加工集（即 g=2).所有工件的加工长度属于[1,?] (?≥1).目标函数是最大化最小机器装载量. 用三参数表示法表示为P|GOS(g=2),pj G [1,?],online,over-list|Cmin.这里的工件是按顺序到达的，只有当前已经到达的工件被安排之后，下一个工件才会到达.工件到达之后会被立即安排. 在本章中机器被分为两层.第一层机器可以加工所有的工件，但第二层机器只能加工特定的工件.我们给出了竞争比为 1+^3的最好可能的在线算法，其中k= 1 或 k= m-1.其中k表示第一层机器的数目.

目录

第一个书签之前