本書主要介紹若干平行批處理機(jī)生產(chǎn)模型的解決方案, 即設(shè)計(jì)有效的算法從而得到較好的生產(chǎn)計(jì)劃。平行批處理機(jī)問(wèn)題的特點(diǎn)是每一臺(tái)加工機(jī)器可以同時(shí)加工多個(gè)任務(wù), 目標(biāo)是設(shè)計(jì)合理的生產(chǎn)安排使得效率更高。同時(shí)在生產(chǎn)過(guò)程中加工任務(wù)允許中斷重啟。這意味著當(dāng)新任務(wù)到達(dá)時(shí)可以中斷正在加工的任務(wù), 并和新任務(wù)重新開始一起加工。與不允許加工任務(wù)中斷相比, 允許中斷重啟得到的生產(chǎn)安排往往更加高效。本書介紹了多個(gè)允許中斷重啟的平行批處理機(jī)生產(chǎn)模型的應(yīng)用背景及高效生產(chǎn)計(jì)劃。
1 緒論
1.1 排序論概述
1.2 算法和計(jì)算復(fù)雜*
1.3 排序的相關(guān)知識(shí)及進(jìn)展
******2 允許有限重啟的多臺(tái)平行批處理機(jī)排序問(wèn)題
******2.1 問(wèn)題介紹 2.2 算法A(α)及相應(yīng)排序的*質(zhì)
******2.3 問(wèn)題的下界
2.4 在線算法
3 允許有限重啟的單臺(tái)平行批處理機(jī)排序問(wèn)題
3.1 問(wèn)題介紹 3.2 批容量為2時(shí)問(wèn)題的下界
3.3 批容量為2時(shí)的在線算法及競(jìng)爭(zhēng)比分析
3.4 批容量大于2時(shí)問(wèn)題的下界
3.5 批容量大于2時(shí)的在線算法及競(jìng)爭(zhēng)比分析
4 允許重啟的單臺(tái)平行批處理機(jī)排序問(wèn)題
******4.1 問(wèn)題介紹
4.2 批容量為3時(shí)問(wèn)題的下界
******4.3 批容量為3時(shí)的在線算法及競(jìng)爭(zhēng)比分析
4.4 批容量大于3時(shí)問(wèn)題的下界
4.5 批容量大于3時(shí)的在線算法及競(jìng)爭(zhēng)比分析
******4.6 允許k-有限重啟(k≥2)時(shí)的問(wèn)題
5 帶有重啟和運(yùn)輸?shù)钠叫信幚頇C(jī)排序問(wèn)題
5.1 問(wèn)題介紹
5.2 批容量為2時(shí)問(wèn)題的下界
******5.3 批容量為2時(shí)的在線算法及競(jìng)爭(zhēng)比分析
5.4 批容量大于2時(shí)問(wèn)題的下界
5.5 批容量大于2時(shí)的在線算法及競(jìng)爭(zhēng)比分析
參考文獻(xiàn)