带有加工机器约束的若干在线排序问题研究

发布时间：2020-07-29 14:26

【摘要】：本文主要研究的是带有加工机器约束的平行机在线排序问题。在此问题中,每个工件都对应一个到达时间rj,一个加工时间pj和一个加工机器集合Mj,工件只能在时刻rj之后被安排到Mj中的某个机器上加工,加工需要占用pj个单位时间。我们考虑这个问题的在线情形。也就是说,只有在此工件到达之后,我们才能得到这个工件的完整信息,甚至包括它是否存在。而在此工件到达后,我们可以选择立刻安排它,或者将此工件推迟到之后的某个时间再进行安排。我们的目标是最小化时间表长。我们考虑的是此问题的四种特殊情形:嵌套加工机器集合、包含加工机器集合、树型加工机器集合以及区间加工机器集合。在第二章,我们考虑的是嵌套加工机器集合的情形。在我们的问题中,机器数目是任意的且工件都带有相同的加工时间。对于此问题,我们给出算法H1,在此算法中,我们将工件安排在时刻αp+kp(α=(?)/2,k= 0,1,2,...)加工,并且在任意时刻,我们优先安排带有最小|Mj|的工件。算法H1的竞争比为(?)/2并且此算法是该问题的最优在线算法。在第三章,我们考虑的是包含加工机器集合的情形。首先我们考虑的问题是所有工件带有相同的加工时间且机器数是任意的。对于此问题,我们给出算法H2。H2与H1较为类似,不同的是我们不仅将工件安排在αp+kp时刻加工,还将工件安排在2αp + kp时刻加工,其中α =(?)-1,k= 0,1,2,...。我们证明了算法H2的竞争比为(?)并且它是此问题的最优在线算法。之后我们考虑的问题是机器数为2且工件的加工时间是任意的。同样我们给出了此问题的最优在线算法。在第四章,我们考虑的是树型加工机器集合。首先我们考虑的是机器数为3且工件的加工时间为任意的情形。我们证明了此问题的下界为3/2,并给出了此问题的最优在线算法。之后,我们考虑了树型图的一种特殊情形:星型图。我们考虑的是机器数为任意且工件都带有相同加工时间的情形。我们证明了此问题的下界为(?)并给出了此问题的最优在线算法。在第五章,我们考虑的是区间加工集合的情形。在我们考虑的问题中,工件的加工时间都相同且只有两种不同的加工机器集合。我们给出了此问题的下界为3/2,并给出了此问题的最优在线算法。
【学位授予单位】：华东理工大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O223
【图文】：

树型,机器,加工机,工件

中的每一个结点代表一台机器，每一个工件都对应一个结点，并且此工件所对逡逑应的结点到根节点的唯一的路上的所有结点（也就是机器）所组成的机器集合逡逑就是该工件的加工机器集合。图１．１就是一种树形加工机器集合的情形，其中工逡逑件九Ｊ２，邋Ｊ３，邋Ｊ４分别对应的是机器结点Ｍ２，邋Ａｆ２，邋Ｍ３，邋Ａｆ６，那么它们的加工机器集合分别逡逑为＝邋＿Ｍ２邋＝邋｛`e，鸠｝，＝邋｛Ｍ１；邋Ｍ２，邋Ｍ３｝，＝邋｛Ｍｌ邋Ｍ５，邋Ａｆ６｝。逡逑在区间加工机器集合情形中，所有的机器按某个顺序排序为．．，ＡＵ，任逡逑意的工件，？对应到两个机器的下标％和６＾％邋Ｓ邋￣），则由机器ｉｌｆｙ，Ｍｔ＋１，Ｍ￣＋２，．．．，逡逑组成的机器集合即为工件七的加工机器集合。例如我们现在有四个机器Ａｔ邋Ａｆ２，邋ｉｌ／３，邋ｉ＼／４逡逑和三个工件九九邋Ｊ３，且刈１邋＝逦＝邋｛ＡＪ２，Ｍ３｝，Ｍ３邋＝邋｛ｉ＼／２，Ｍｉ，Ｍ４｝，逡逑则此情形是区间加工机器集合情形。逡逑显然

【参考文献】