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