| A HEURISTIC FOR F3/bi= b/C_(max) AND ITSWORST-CASE ANALYSIS |
| |
| 引用本文： | HOU Sixiang (China Marine Development and Research Cented Box 1303-17,Beijing 100073,China) DU Donglei (Institute of Applied Mathematics,Academia Sinica,Beijing 100080,China). A HEURISTIC FOR F3/bi= b/C_(max) AND ITSWORST-CASE ANALYSIS[J]. 系统科学与复杂性, 1997, 0(2) |
| |
| 作者姓名： | HOU Sixiang (China Marine Development and Research Cented Box 1303-17 Beijing 100073 China) DU Donglei (Institute of Applied Mathematics Academia Sinica Beijing 100080 China) |
| |
| 作者单位： | HOU Sixiang (China Marine Development and Research Cented Box 1303-17，Beijing 100073，China) DU Donglei (Institute of Applied Mathematics，Academia Sinica，Beijing 100080，China) |
| |
| 摘 要： | 1.IntroductionTheF3Cm..canbestatedasfOllows.Eachofthenjobs1,2,'')nistobeprocessedonthreemachinesA,B,Cinthesameorder.Giventheprocessingtimesal?hiandciofjobionmachinesA,BandC,findtheorderinwhicheachmachineshouldprocessethejobssoastominimizingthetotaltimesp…
|
A HEURISTIC FOR F3/bi= b/C_(max) AND ITS WORST-CASE ANALYSIS |
| |
| HOU Sixiang. A HEURISTIC FOR F3/bi= b/C_(max) AND ITS WORST-CASE ANALYSIS[J]. Journal of Systems Science and Complexity, 1997, 0(2) |
| |
| Authors: | HOU Sixiang |
| |
| Abstract: | This paper describes a heuristic for solving F3/bi = b/Cmax scheduling problem. This algorithm first uses the Johnson's algorithm solving F2Cmax, then, presents revised algorithm to solve F3/bi = b/Cmax. Lastly, an O(n log n) time heuristic is presented which generates a schedule with length at most 3/2 times that of an optimal schedule, for even number n 4, and 3/2 1/(2n) times that of an optimal schedule, for odd number n 4. These bounds are tight. |
| |
| Keywords: | Two-machine flow shop three-machine flow shop worst-case analysis automated manufacturing system heuristic. |
| 本文献已被 CNKI 等数据库收录！ |
