本研究探討等速率平行機台(Uniform Parallel Machine)之排程問題,考慮n個工件f個群組在m台等速率平行機台上加工,工件具有抵達時間和群組限制,同一部機台上,如果正準備處理的工件與上一個工件所屬群族不同時,則必須加上整備時間。本研究以總延遲時間最小化為目標。 首先,利用啟發式演算法,將群組排入機台,以減少整備時間,再利用貪婪演算法找出重複時間(Overlap)較大的群組,移除工件並嘗試排入機台上每個位置,排入機台時需考慮工件之抵達時間,直到找到最小總延遲時間則停止。本研究在機台數為30台、群組數為50個、工件量為512個,當處理時間為[1,100]時,求解時間為248.02秒。
We consider the problem of scheduling n jobs with f families on m uniform parallel machines. Every job has arrival time and belongs to one family. We have to add setup time when machine is processing one job( this job’s family is different to last job ). Our objective is to minimize total tardiness. First, we use heuristic assign family into machine for reducing setup time then we find families with greater overlap and using greedy algorithm to remove jobs from machine . For those jobs witch are removed we try assign them into every position. When we are assigning jobs into machine , we must consider it’s arrival time. The average execution time of problem with 30 machines, 50 families, 512 jobs and processing time [1,00] can be solved in 286.79 seconds.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。