本文討論了帶有機(jī)器準(zhǔn)備時(shí)間和加工資格限制的平行機(jī)排序,分別研究了目標(biāo)函數(shù)為最大完工時(shí)間和最大延誤時(shí)間的極小化問題.論文首先分析問題的NP-難性,然后討論問題在多種特殊情形下的最優(yōu)算法,最后在此基礎(chǔ)上對原問題提出時(shí)間復(fù)雜度較好的啟發(fā)式算法.第一部分,考慮極小化最大完工時(shí)間問題.首先針對問題Pm,Ri|pj=p,Mj|Cmax給出了時(shí)間復(fù)雜度分別為O(m3/2n5/2logmn)和O(n logn)的最優(yōu)算法,然后針對問題Pm,Ri| Mj| Cmax提出了三個(gè)時(shí)間復(fù)雜度均為O(n log n)的啟發(fā)式算法.第二部分,考慮極小化最大延誤問題.首先分別證明了問題Pm,Ri| pj=1,Mj|Lmax、問題Pm | intree,pj=1,Mj| Lmax 和問題 P2 | prec,pj=1,Mj| Lmax 存在時(shí)間復(fù)雜度為O(n log n)、O(n log n)和O(n2)的最優(yōu)算法,然后針對問題Pm,Ri|Mj| Lmax提出了時(shí)間復(fù)雜度為O(nlogn)的啟發(fā)式算法.第三部分,考慮帶有機(jī)器準(zhǔn)備時(shí)間、加工資格限制和工件準(zhǔn)備時(shí)間的平行機(jī)排序問題.針對問題Pm,Ri|rj,Mj| Cma...

【文章頁數(shù)】：50 頁

【學(xué)位級別】：碩士

【文章目錄】：
中文摘要
Abstract
第一章 引言
    1.1 研究背景及現(xiàn)狀
    1.2 現(xiàn)有算法及結(jié)論
    1.3 假設(shè)和符號說明
    1.4 研究內(nèi)容及結(jié)構(gòu)
第二章 帶有機(jī)器準(zhǔn)備時(shí)間和加工資格限制的極小化最大完工時(shí)間問題
    2.1 問題的NP-難性及可解性分析
    2.2 問題P_m,R_i|p_j=p,M_j|Cmax

    2.3 問題P_m,R_i|p_j,M_j|C_max

第三章 帶有機(jī)器準(zhǔn)備時(shí)間和加工資格限制的極小化最大延誤時(shí)間問題
    3.1 問題的NP-難性及可解性分析
    3.2 問題P_m,R_i|p_j=1,M_j|L_max

    3.3 問題P_m,R_i|p_j,M_j|L_max

第四章 帶有機(jī)器、工件準(zhǔn)備時(shí)間和加工資格限制的平行機(jī)排序問題
    4.1 問題P_m,R_i|p_j,r_j,M_j|C_max

    4.2 問題P_m,R_i|p_j,r_j,M_j|L_max

第五章 總結(jié)和展望
    5.1 研究總結(jié)
    5.2 研究展望
參考文獻(xiàn)
致謝



本文編號：3940469

suoshi