可用性及位置限制下的单机排序研究
发布时间：2018-11-17 09:28
【摘要】：在实际生产过程中,机器并不是不间断地在工作.机器维修、机器定期检查等因素使得机器的可用性受到限制.本学位论文考虑的机器可用性限制指的是:机器上有一个禁用区间.工件带有位置限制指的是每个工件都必须在它被指定的位置之前在机器上进行加工.本文综合考虑了以上两个因素,并研究机器具有可用性限制并且工件具有位置限制的若干单机排序问题.本文研究的内容主要分为两部分.第一部分研究可中断情形下单台机器带有一个禁用区间[R,D]并且每个工件都有位置限制的排序模型.第二部分研究不可中断情形下单台机器带有一个禁用区间[R,D]并且每个工件都有位置限制的排序模型.我们用h1表示机器上只有一个禁用区间的限制,用σ[Jj]≤kj表示工件Jj必须在前kj个位置在机器上进行加工的限制.在第二章,我们所研究的排序问题有:·工件可中断最小化最大延迟排序问题1,h1|σ[Ji]≤kj,pmtn|Lmax.·工件可中断最小化完工时间和排序问题1,h1|σ[Ji]≤kj,pmtn|ΣCj.·工件可中断最小化最大费用排序问题1,h1|σ[Jj]≤kj,pmtn|fmax.针对以上三个问题,我们分别给出了多项式时间算法.在第三章,我们所研究的排序问题有:·工件不可中断最小化完工时间和排序问题1,h1|σ[Jj]≤kj|∑Cj.针对上述问题,在第3.2节,我们给出了一个2-近似算法.在第3.3节,我们证明了,如果对某些工件的长度加以限制,则存在一个20/17-近似算法.在第3.4节,在与第3.3节相同的限制条件下,我们给出了一个多项式时间近似方案(PTAS).
[Abstract]:In the actual production process, the machine is not continuously working. The availability of machines is limited by such factors as machine maintenance and periodic inspection of machines. The machine availability limit considered in this dissertation is that there is a disabling range on the machine. A workpiece with a position limit means that each workpiece must be processed on the machine before it is assigned a position. In this paper, the above two factors are comprehensively considered, and some single machine scheduling problems with availability constraints and workpiece location constraints are studied. The content of this paper is divided into two parts. In the first part, we study the ordering model with a disabling interval [RPU D] and a location limit for each artifact. In the second part, we study the ordering model of an uninterrupted ordering machine with a disabling interval [RPU D] and a location limit for each artifact. We use H1 to denote the restriction that there is only one forbidden interval on the machine, and 蟽 [Jj] 鈮，
本文编号：2337292
[Abstract]:In the actual production process, the machine is not continuously working. The availability of machines is limited by such factors as machine maintenance and periodic inspection of machines. The machine availability limit considered in this dissertation is that there is a disabling range on the machine. A workpiece with a position limit means that each workpiece must be processed on the machine before it is assigned a position. In this paper, the above two factors are comprehensively considered, and some single machine scheduling problems with availability constraints and workpiece location constraints are studied. The content of this paper is divided into two parts. In the first part, we study the ordering model with a disabling interval [RPU D] and a location limit for each artifact. In the second part, we study the ordering model of an uninterrupted ordering machine with a disabling interval [RPU D] and a location limit for each artifact. We use H1 to denote the restriction that there is only one forbidden interval on the machine, and 蟽 [Jj] 鈮，
本文编号：2337292
本文链接：https://www.wllwen.com/kejilunwen/yysx/2337292.html
