| A New Local Search Algorithm for the Job Shop Scheduling Problem |
| |
| 作者姓名： | Huang Wen\|qi Yin Ai\|hua . School of Computer Science and Technology Huazhong University of Science and Technology Wuhan Hubei China . School of Mathematics and Computer Science Hubei University Wuhan Hubei China |
| |
| 作者单位： | Huang Wen\|qi 1，Yin Ai\|hua 1，2 1. School of Computer Science and Technology，Huazhong University of Science and Technology，Wuhan 430074，Hubei，China; 2. School of Mathematics and Computer Science，Hubei University，Wuhan 430062，Hubei，China |
| |
| 基金项目： | ChinaNational 973Program
(G1 9980 30 60 0 ) |
| |
| 摘 要： | 0 IntroductionThejobshopschedulingproblemwithwhichwearecon cernedconsistsinschedulingasetofjobsonasetofma chinesfortheobjectiveofminimizingthemake span ,i.e .themaximumoftimeneededforfinishingalljobs,whichissubjecttotheconstrainsthateachjobhasafixedprocessingorderthroughthemachinesandeachmachinecanprocessatmostonejobatatime .ThisproblemisNP hardandevenisoneofthehardestcom binationaloptimizationproblems.Itiswellknownthatonlysmallsizeprobleminstancescanbesolvedwithinareasonablecomputa tionalti…
|
A new local search algorithm for the job shop scheduling problem |
| |
| Huang Wen\|qi ,Yin Ai\|hua , . School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan ,Hubei,China, . School of Mathematics and Computer Science,Hubei University,Wuhan ,Hubei,China.A New Local Search Algorithm for the Job Shop Scheduling Problem[J].Wuhan University Journal of Natural Sciences,2003,8(3):797-802. |
| |
| Authors: | Wen-qi Huang Ai-hua Yin |
| |
| Affiliation: | (1) School of Computer Science and Technology, Huazhong University of Science and Technology, 430074 Wuhan, Hubei, China;(2) School of Mathematics and Computer Science, Hubei University, 430062 Wuhan, Hubei, China |
| |
| Abstract: | In this paper, the job shop scheduling problem concerned with minimizing make\|span is discussed, and a new local search algorithm is proposed for it. This local search method is based on an improved shifting bottleneck procedure and Tabu Search technique. This new local search is different from the previous Tabu Search (TS) proposed by other authors, which is because the improved shifting bottleneck procedure is a new technology that is provided by us for the problem, and two remarkable strategies--intensification and diversification of TS are modified. To demonstrate the performance, our algorithm has been tested on many common problem instances (benchmarks) with various sizes and levels of hardness and compared with other algorithms, especially the latest TS in the literatures. Computational experiments show that this algorithm is effective and efficient. |
| |
| Keywords: | heuristic improved shifting bottleneck procedure Tabu search intensification diversification |
| 本文献已被 CNKI 万方数据 SpringerLink 等数据库收录！ |
