本文研究了若干新型排序問題,主要包括工件可拒絕的平行機代理排序問題、工件帶退化和拒絕的分批排序問題、工件帶退化和拒絕的多代理排序問題、帶有人員不可用區(qū)間的兩臺機器流水車間排序問題以及工件可拒絕的供應(yīng)鏈排序問題五個方面。針對不同的問題,我們分別給出了相應(yīng)的算法,并對一些問題的計算復(fù)雜性進行了分析。第一章首先給出了組合優(yōu)化和排序論方面的一些基本概念和定義,然后介紹了與本文內(nèi)容相關(guān)方向的研究現(xiàn)狀,最后介紹了本文的主要研究成果。第二章研究了工件可拒絕的平行機代理排序問題。給定兩個代理A和B以及兩臺平行機,每個代理有一批工件需要在機器上加工,兩個代理的工件互不相同。對于任意一個工件,可以被拒絕并支付一定的拒絕費用,或者被接受并安排在機器上加工。目標是在代理B的接受工件對應(yīng)的目標函數(shù)fB與拒絕B-工件的總拒絕費用之和不超過一給定上界的情況下,極小化代理A的接受工件對應(yīng)的目標函數(shù)fA與拒絕A-工件的總拒絕費用之和,其中fA和fB分別是關(guān)于代理A和代理B的接受工件的完工時間的正則函數(shù)。我們研究了四種不同的目標函數(shù)組合,fA=∑CjA,fB∈（?）當（fA,fB）={∑CjA,CmaxB),我們給出了兩... 

【文章來源】：華東理工大學(xué)上海市 211工程院校 教育部直屬院校

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

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 組合優(yōu)化問題
    1.2 算法和計算復(fù)雜性
    1.3 排序問題簡介
    1.4 文獻綜述
    1.5 論文概述
第2章 工件可拒絕的兩代理平行機排序問題
    2.1 引言
    2.2 問題描述
max
B+∑_Ji^B∈RB ej
B≤Q|∑Ji
A∈AA Cj
A+∑Jj
A∈R_A ej
A">    2.3 問題 P2|rej,Cmax
B+∑_Ji^B∈RB ej
B≤Q|∑Ji
A∈AA Cj
A+∑Jj
A∈R_A ej
A

        2.3.1 動態(tài)規(guī)劃算法
        2.3.2 近似算法
max
B+∑J_{j
B∈RB ej
B≤Q|∑Jj
A∈AA Cj
A+∑Jj
A∈RA ej
A">    2.4 問題 P2|rej,Lmax
B+∑Jj
B∈RB ej
B≤Q|∑Jj
A∈AA Cj
A+∑Jj
A∈RA ej
A}

    2.5 問題 P2|rej,∑w_{j
BUj
B≤Q|∑Jj
A∈AA Cj
A+∑Jj
A∈RA ej
A}

第3章 工件帶退化和拒絕的兩代理單機排序問題
    3.1 引言
    3.2 問題描述
j
X=b_{j
X（a+bt）,Cmax
B+∑ej
B≤Q|∑Cj
A+∑ej
A">    3.3 問題 1|rej,pj
X=bj
X（a+bt）,Cmax
B+∑ej
B≤Q|∑Cj
A+∑ej
A}

        3.3.1 動態(tài)規(guī)劃算法
        3.3.2 近似算法
j
X=b_{j
X（a+bt）,∑Cj
B+∑ej
B≤Q|∑Cj
A+∑ej
A">    3.4 問題 1|rej,pj
X=bj
X（a+bt）,∑Cj
B+∑ej
B≤Q|∑Cj
A+∑ej
A}

第4章 工件帶退化和拒絕的單機批處理排序問題
    4.1 引言
    4.2 問題描述
max的情形">    4.3 最大完工時間C_max的情形
        4.3.1 復(fù)雜性分析
j=b_jt,r_j,b=∞,∑J_j∈R e_j≤Q|C_max">        4.3.2 問題 1|rej,p-batch,p_j=b_jt,r_j,b=∞,∑J_j∈R e_j≤Q|C_max

        4.3.3 問題 1|rej,p-batch,p_j=b_jt,r_j,b=∞,C_max≤Y|∑J_j∈R e_j

    4.4 加權(quán)總完工時間∑J_i∈A w_jC_j的情形
        4.4.1 復(fù)雜性分析
j=b_jt,b=∞,∑J_j∈R e_j≤Q|∑J_j∈A w_jC_j">        4.4.2 問題 1|rej,p-batch,P_j=b_jt,b=∞,∑J_j∈R e_j≤Q|∑J_j∈A w_jC_j

        4.4.3 問題 1|rej,p-batch,P_j=b_jt,b=∞,∑J_i∈R e_j≤Q|T_max

    4.5 問題 1|rej,p-batch,P_j=b_jt,b=∞,∑J_j∈R e_j≤Q|T_max

第5章 帶有人員不可用區(qū)間的流水車間排序問題
    5.1 引言
    5.2 符號說明及基本性質(zhì)
    5.3 復(fù)雜性分析
    5.4 近似算法
第6章 工件可拒絕的供應(yīng)鏈排序問題的一個改進算法
    6.1 引言
    6.2 問題描述及基本性質(zhì)
    6.3 近似算法
第7章 結(jié)論與展望
參考文獻
致謝
博士在讀期間完成的論文


【參考文獻】：
博士論文
[1]帶不可用時間段的若干單機供應(yīng)鏈排序問題的算法研究[D]. 范靜.華東理工大學(xué) 2015
[2]機器帶使用限制的若干排序問題的算法研究[D]. 李剛剛.華東理工大學(xué) 2015



本文編號：3015250

boshi