同類機半在線機器覆蓋問題研究
論文摘要: 本文主要研究兩臺同類機半在線機器覆蓋問題.全文共分為三章. 第一章是緒論部分,主要介紹排序問題,近似算法和競爭比分析等基本概念. （略）主要研究了兩臺同類機已知工件總加工時間的半在線模型,目標是極大化最�。裕�.根據機器速度之比s的不同,我們分別給出了優先考慮速度快的機器的算法FF(當1≤s≤(1+5（略）)/2時)和優先考慮速度慢的機器的算法SF(當s>(1+5~(1/2))/2時).并且證明了這兩個算法都是最優的,競爭比是: 第三章主要研究了兩臺同類機已知工件最大加工時間的半在線模型,目標是極大化最小機器完工時間.根據機器速度之比s的不同,我們分別給出了優先考慮速度快的機器的算法FFLS(當1≤s≤(1+5~(1/2))/2時)和優先考慮速度慢的機器的（略）(當s>(1+5~(1/2))/2時).其中算法FFLS對1≤s≤(1+5~(1/2))/2是最優的,算法SFLS對s∈[1.618,2.1479)∪(3.83598,+∞)是最優的,在s∈（略）9,3.83598)時,算法SFLS的競爭比和問題的下界的差距最多不超過0...
This thesis mainly concerns design and analy（omitted）roximation algorithms on semi-online uniform machine covering problems. We first introduc（omitted）tions scheduling problem, approximation algorithms and competitive analysis.In Chapter 2, we investigate semi-online scheduling （omitted） two uniform machines, where the total size of all jobs is known in advance, the objective is to maximize （omitted）m load of two machines. We present two optimal algorithms FF for and （omitted）espectively. FF gives pref...
目錄:摘要 第4-5頁
Abstract 第5頁
第1章 緒論 第7-15頁
·排序問題 第7-8頁
·近似算法和競爭比分析 第8-9頁
·半在線排序問題 第9-10頁
·西臺同類機在線半在線排序問題 第10-12頁
·論文綜述 第12-15頁
第2章 已知工件總加工時間的兩臺同類機排序 第15-22頁
·問題Q2|sum|C_(min)的下界 第15-16頁
·問題Q2|sum|C_(min)的最優算法 第16-22頁
第3章 已知最大工件加工時間的兩臺同類機排序 第22-35頁
·問題Q2|max|C_(min)的下界 第22-24頁
·問題Q2|max|C_(min)的算法 第24-35頁
參考文獻 第35-37頁
致謝 第37-38頁
在學期間完成的論文 第38頁
【同類機半在線機器覆蓋問題研究】相關文章：
機器帶中斷的若干延誤問題研究論文提綱11-18
考慮節能降耗的關鍵機器調度問題研究11-18
林權在線競價信任機制研究提綱11-29
變電設備在線檢測技術的應用研究03-03
企業品牌經營問題研究11-15
教學的存在問題及對策研究11-14
企業采購管理問題研究03-30
在線高校畢業生檔案管理系統的研究02-25
企業債務重組問題的研究論文01-12
- 相關推薦