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