具有等間隔工期的2臺(tái)機(jī)器流水作業(yè)調(diào)度問(wèn)題的強(qiáng)NP難性
浙江大學(xué)學(xué)報(bào)(理學(xué)版)
頁(yè)數(shù)： 6 2024-09-18
摘要： 考慮3個(gè)具有等間隔工期的雙機(jī)流水作業(yè)調(diào)度問(wèn)題，其中按照調(diào)度方案中工件的加工順序給每個(gè)工期分配工件，且2個(gè)連續(xù)工期之間的間隔長(zhǎng)度相同，目標(biāo)分別為最小化最大延誤、總延誤和總誤工工件數(shù)。證明了此三問(wèn)題均為強(qiáng)NP-難的。此外，結(jié)果表明，如果P≠NP，那么這些問(wèn)題沒(méi)有偽多項(xiàng)式時(shí)間算法和完全多項(xiàng)式時(shí)間近似方案（FPTAS）。 （共6頁(yè)）
APP 