【摘要】：在實(shí)際生產(chǎn)過程中,機(jī)器并不是不間斷地在工作.機(jī)器維修、機(jī)器定期檢查等因素使得機(jī)器的可用性受到限制.本學(xué)位論文考慮的機(jī)器可用性限制指的是:機(jī)器上有一個(gè)禁用區(qū)間.工件帶有位置限制指的是每個(gè)工件都必須在它被指定的位置之前在機(jī)器上進(jìn)行加工.本文綜合考慮了以上兩個(gè)因素,并研究機(jī)器具有可用性限制并且工件具有位置限制的若干單機(jī)排序問題.本文研究的內(nèi)容主要分為兩部分.第一部分研究可中斷情形下單臺(tái)機(jī)器帶有一個(gè)禁用區(qū)間[R,D]并且每個(gè)工件都有位置限制的排序模型.第二部分研究不可中斷情形下單臺(tái)機(jī)器帶有一個(gè)禁用區(qū)間[R,D]并且每個(gè)工件都有位置限制的排序模型.我們用h1表示機(jī)器上只有一個(gè)禁用區(qū)間的限制,用σ[Jj]≤kj表示工件Jj必須在前kj個(gè)位置在機(jī)器上進(jìn)行加工的限制.在第二章,我們所研究的排序問題有:·工件可中斷最小化最大延遲排序問題1,h1|σ[Ji]≤kj,pmtn|Lmax.·工件可中斷最小化完工時(shí)間和排序問題1,h1|σ[Ji]≤kj,pmtn|ΣCj.·工件可中斷最小化最大費(fèi)用排序問題1,h1|σ[Jj]≤kj,pmtn|fmax.針對(duì)以上三個(gè)問題,我們分別給出了多項(xiàng)式時(shí)間算法.在第三章,我們所研究的排序問題有:·工件不可中斷最小化完工時(shí)間和排序問題1,h1|σ[Jj]≤kj|∑Cj.針對(duì)上述問題,在第3.2節(jié),我們給出了一個(gè)2-近似算法.在第3.3節(jié),我們證明了,如果對(duì)某些工件的長(zhǎng)度加以限制,則存在一個(gè)20/17-近似算法.在第3.4節(jié),在與第3.3節(jié)相同的限制條件下,我們給出了一個(gè)多項(xiàng)式時(shí)間近似方案(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] 鈮，

本文編號(hào)：2337292