工件具有相容性的平行分批在线排序问题

发布时间：2018-04-26 19:29

  本文选题：在线排序 + 相容性　； 参考：《中国矿业大学》2017年硕士论文

【摘要】：所谓排序,即在一定的资源限制下更好地安排和完成一些任务,使得期望的效益或目标达到最优值或理想值。排序论在工业制造领域,计算机科学,物流运输管理等领域都有广泛地应用,具有重要的理论研究价值和广泛的应用前景。本论文主要研究的是工件具有相容性的多台平行分批处理机的在线排序问题。在线排序是指每个工件都有一个到达时间,决策者在工件到达之后才知晓其信息。对到达的工件,排序者可以立即安排加工,也可推迟安排加工。平行分批排序是指工件在加工过程中被分成若干批,每个批中允许同时放置多个工件,但工件总数不得超过批容量。批容量通常分为有限和无限两种情形。同一批中的工件有相同的开工时间和完工时间。批的加工时间定义为该批中加工时间最大的工件的加工时间。工件具有相容性约束一般分为两种类型:(1)工件具有区间相容性;(2)工件属于不同的工件组。工件具有区间相容性是指,每一个工件都有一个可以用区间表示的信息,两个工件相容当且仅当两工件的区间相交,此时,二者可以放在同一个批中加工。工件属于不同工件组是指任意一个工件都属于某个确定的工件组,只有同一个工件组中的工件才能够放在同一个批中加工。本文研究的排序问题的目标函数是最小化最大完工时间。本文的主要成果如下:(1)对排序问题pm=|on-line,rj,G=INT,p-batch,b=∞|Cmax,本文证明了任意一个在线算法的竞争比都不小于2,并设计出竞争比为2+(m-1)/(m+1)的在线算法,且该在线算法是单机情形下的一个最优在线算法;对工件加工时间相同的特殊情形,设计出了一个竞争比为2的最优在线算法。(2)对排序问题pm|on-line,rj,family,p-batch,b=∞|Cmax,本文证明了任意一个在线算法的竞争比都不小于2,并设计出了一个竞争比为7/3-1/(3m)的在线算法,且证明这个界是可达的;对工件加工时间相同的特殊情形,设计出了一个竞争比为2的最优在线算法。
[Abstract]:The so-called sorting is to arrange and complete some tasks better under certain resource constraints, so that the desired benefit or goal can reach the optimal value or ideal value. Sequencing theory has been widely used in the field of industrial manufacturing, computer science, logistics and transportation management, etc. It has important theoretical research value and wide application prospect. In this paper, the problem of online scheduling of parallel batch processors with compatible workpiece is studied. On-line sorting means that each artifact has a time of arrival, and the decision maker does not know the information until the arrival of the artifact. To arrive the workpiece, the sorter may arrange the processing immediately, may also delay the arrangement processing. Parallel batch ranking refers to the number of jobs being divided into lots in the process of processing, in which multiple jobs are allowed to be placed simultaneously, but the total number of jobs must not exceed the batch capacity. Batch capacity is usually divided into two cases: finite and infinite. The same batch of workpieces have the same start-up time and completion time. The processing time of the batch is defined as the processing time of the workpiece with the longest processing time in the batch. Jobs with compatibility constraints are generally divided into two types: 1) workpieces have interval compatibility and / or 2) workpieces belong to different workpiece groups. An interval-compatible workpiece means that each workpiece has an information that can be represented by an interval, and that two jobs are compatible if and only if the intersections of two jobs intersect, in which case they can be processed in the same batch. Jobs belonging to different job groups refer to that any job belongs to a certain workpiece group. Only jobs in the same workpiece group can be processed in the same batch. The objective function of the sorting problem studied in this paper is to minimize the maximum completion time. The main results of this paper are as follows: (1) in this paper, we prove that the competition ratio of any online algorithm is not less than 2, and design an online algorithm with a competition ratio of 2 m ~ (-1) / m ~ (1). The on-line algorithm is an optimal on-line algorithm in the case of a single machine, and for the special case where the workpiece processing time is the same, In this paper, we design an optimal online algorithm with a competition ratio of 2. We design an online algorithm for the ordering problem: pm on-line family p-batchnb = 鈭，

本文编号：1807373