本文選題：簡單線性惡化 + 不可用時間限制��； 參考：《運籌學學報》2016年04期

【摘要】：研究的單機供應鏈排序問題中,機器有一個不可用時間限制,工件的加工時間與惡化率及其開工時間有關,且工件的加工不可恢復.一個或多個完工工件可組成一個發(fā)送批由車輛發(fā)送給客戶,且在機器不可用時間限制之前完工的工件必須在限制開始之時或之前完成發(fā)送.問題的目標是最小化總發(fā)送時間與總發(fā)送費用之和.證明問題是NP-難的,提出了偽多項式時間的動態(tài)規(guī)劃算法.進一步,在確定問題目標函數(shù)值的上界及下界之后,設計了一個完全多項式時間近似方案(FPTAS).
[Abstract]:In the single machine supply chain scheduling problem, the machine has an unusable time limit, the processing time of the workpiece is related to the deterioration rate and the starting time, and the processing of the workpiece is not recoverable.One or more completed artifacts may form a sending batch to be sent to the customer by the vehicle, and the work completed before the machine is unavailable time limit must be sent at or before the beginning of the limit.The goal of the problem is to minimize the sum of total transmission time and total transmission cost.To prove that the problem is NP-hard, a pseudo polynomial time dynamic programming algorithm is proposed.Furthermore, after determining the upper and lower bounds of the value of the objective function of the problem, a complete polynomial time approximation scheme is designed.
【作者單位】： 上海工業(yè)大學文理學部;華東理工大學理學院;
【基金】：國家自然科學基金青年項目(No.11601316) 上海第二工業(yè)大學青年教師培養(yǎng)科研項目(No.201513)
【分類號】：O223

【相似文獻】

相關期刊論文 前5條

1 馬英;左春榮;楊善林;;帶不可用時間段和惡化加工時間的單機調(diào)度[J];系統(tǒng)工程學報;2010年03期

2 馬英;楊善林;儲誠斌;;帶不可用時間段的部分可續(xù)型單機最大完工時間調(diào)度[J];系統(tǒng)工程理論與實踐;2009年04期

3 馬英;左春榮;楊善林;;帶不可用時間段的兩臺同類機加權(quán)完工時間和調(diào)度[J];中國科學技術(shù)大學學報;2009年06期

4 王海明;劉吉紅;王慶磊;;帶不可用時間段的不允許等待柔性流水排序問題[J];蘭州大學學報(自然科學版);2007年01期

5 ;[J];;年期

相關博士學位論文 前1條

1 范靜;帶不可用時間段的若干單機供應鏈排序問題的算法研究[D];華東理工大學;2015年

，

本文編號：1753564