本文選題：組合優(yōu)化 + 批排序問題　； 參考：《高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯》2017年04期

【摘要】：研究單臺(tái)機(jī),工件加工時(shí)間相等,大小不同的批排序問題,給出了一個(gè)最壞情況界為9+3~(1/2)/6≈1.7817的多項(xiàng)式時(shí)間近似算法,并證明了即使工件總大小不超過2,該問題也不存在FPTAS,除非P=NP.
[Abstract]:In this paper, we study the batch scheduling problem of a single machine with equal workpiece processing time and different size. A polynomial time approximation algorithm with a worst-case bound of 9.3 ~ (1 / 2) / 6 鈮，

本文編號(hào)：2052313