本文選題：排序　切入點(diǎn)：流水作業(yè)　出處：《運(yùn)籌學(xué)學(xué)報(bào)》2017年02期

【摘要】：考慮了工件具有退化效應(yīng)的兩臺機(jī)器流水作業(yè)可拒絕排序問題,其中工件的加工時(shí)間是其開工時(shí)間的簡單線性增加函數(shù).每個(gè)工件或者被接收,依次在兩臺流水作業(yè)機(jī)器上被加工,或者被拒絕但需要支付一個(gè)確定的費(fèi)用.考慮的目標(biāo)是被接收工件的最大完工時(shí)間加上被拒絕工件的總拒絕費(fèi)用之和.證明了問題是NP-難的,并提出了一個(gè)動態(tài)規(guī)劃算法.最后對一種特殊情況設(shè)計(jì)了多項(xiàng)式時(shí)間最優(yōu)算法.
[Abstract]:In this paper, we consider the problem that two machines with degenerative effect have the problem of rejection and ordering of flow jobs, in which the processing time of the workpiece is a simple linear increase function of its starting time, and each workpiece is either received or received. In turn, they are processed on two flow machines, The goal is the maximum completion time of the received workpiece plus the sum of the total rejection cost of the rejected workpiece. It proves that the problem is NP-hard. A dynamic programming algorithm is proposed, and a polynomial time optimal algorithm is designed for a special case.
【作者單位】： 曲阜師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院;
【基金】：國家自然科學(xué)基金(No.11201259) 教育部博士點(diǎn)基金(Nos.20123705120001,20123705110003) 山東省自然科學(xué)基金(Nos.ZR2015GZ009,ZR2014AM012,ZR2014AM021) 曲阜師范大學(xué)科研獎(jiǎng)勵(lì)基金(No.xkj201516)
【分類號】：O223
，

本文編號：1655405