《一种改进的作业车间调度转换瓶颈算法》由会员分享，可在线阅读，更多相关《一种改进的作业车间调度转换瓶颈算法（13页珍藏版）》请在金锄头文库上搜索。
1、http:/ A Modified Shifting Bottleneck Procedure for Job Shop Scheduling 1Zhi Huang College of Computer Science and Technology，Huazhong University of Science and Technology Wuhan, P. R. China 430074 E-mail： Abstract In this paper, the job shop scheduling problem with the objective to minimize the mak
2、espan is discussed. The theorem, which guarantees the shifting bottleneck procedure (SB) with Schrage one-machine sequencing algorithm always obtains the feasible solution for any instance, is concisely proven. A counterexample is given to show that SB with Carliers one-machine sequencing algorithm
3、could get the infeasible solution. By the way, we also point out a mistake made in the Carliers theorem which Carliers algorithm is based on, and complete it by some modifications. In order to overcome the infeasibility weakness of SB and expect better performance, a modified shifting bottleneck pro
4、cedure (MSB) for job shop scheduling is proposed. The theorem, which ensures MSB get the feasible solution for any instance of the problem, is testified. MSB is tested on a group of benchmark instances. The computational experiment shows that MSB get better solutions than SB. Keywords: Job shop sche
5、duling; Heuristic; Feasibility; Shifting Bottleneck 1 Introduction Job shop scheduling problem is among the hardest combinatorial optimization problems, and is strongly NP-complete1. Many heuristic algorithms have been developed including dispatching priority rules 2, local search 3, shifting bottle
6、neck procedure 4, stimulated annealing 5 and tabu search 7,8. The research results of the problem show that it is hard to obtain good enough solutions only by single search scheme. So the hybrid heuristic methods that combine several heuristic schemes have been proposed. It is known that shifting bo
7、ttleneck procedure and taboo search are widely used in hybrid heuristic methods 9-11. Adams et al. proposed shifting bottleneck procedure 4, and they mentioned that it might obtain infeasible solutions, and they also pointed out that they did not find the case. However, they did not explain why the
8、case might exist, and they did not prove that the case does exist, or prove the case would never happen. Storer et al. 12 mentioned that the simplified implementation of SB they used failed for two instances (1050), and said that they did not know the reason. Strictly speaking, the failure might be
9、caused by the weakness in SB 4, or by the simplified implementation, or even by negligence in programming. Although some researchers 13 discussed the infeasible problem of SB, they did not prove that SB with Carlier one-machine sequencing algorithm 14 will always obtain feasible solutions or give a
10、counterexample testifying an infeasible solution could be reached by SB with Carliers algorithm. And they just prove that in SB, if the one-machine sequencing (OMS) problems are solved with Schrages algorithm 14, no infeasibility could be reached 13. So whether SB based on Carlier OMS algorithm coul
11、d obtain infeasibility is still unknown. In this paper, we construct a counterexample testifying SB using Carliers OMS algorithm does get an infeasible solution. Before giving the counterexample, we present the theorem that in SB, if Schrage 1 Support by the National Grand Fundamental Research 973 P
12、rogram of China(G1998030600). -1- http:/ algorithm is used to solve OMS algorithm, feasible solutions will always be obtained. We prove the theorem in a little more than one page, which is much more concise than the literature 13 does in more than five pages. By the way, there is a mistake in the th
13、eorem used in Carliers OMS algorithm14. Although the paper of Carliers algorithm 14 has 22 citations (according to the search result by google search engine), none of them has found out the mistake. We construct a counterexample to show the error, and correct the theorem by some modifications. On th
14、e purpose of overcoming the feasibility problem of the procedure and gaining better solutions, a procedure named the modified shifting bottleneck procedure (MSB) is suggested. We also prove that MSB could always obtain the feasible solution for any instance of job shop scheduling problem. A group of
15、 benchmark instances are computed to test MSB. The computational results show that the performance of MSB is better than that of SB 4 and ISB 13. Although MSB is not the best one at present, it is a promising algorithm. 2 The SB procedure This section is derived from the literature 4,13,14 and is ne
16、eded for better comprehension of section 3 and 4. 2.1 The Problem The job shop scheduling problem (JSSP) is described as follows 4. Jobs are to be processed on machines with the objective of minimizing the makesapn, i.e. the time needed for processing all jobs (maximum completion time), subject to the constraints that: (i) the sequence of mac
