Fuzzy Sets Based Heuristics for Optimization
The aim of this volume is to show how Fuzzy Sets and Systems can help to provide robust and adaptive heuristic optimization algorithms in a variety of situations. The book presents the state of the art gives a broad overview on the real practical applicat
- PDF / 365,605 Bytes
- 15 Pages / 439 x 666 pts Page_size
- 28 Downloads / 259 Views
J.D. Edwards & Company, Toronto, Ontario, Canada Kyoto Institute of Technology, Kyoto, Japan McMaster University, Hamilton, Ontario, Canada Acadia University, Wolfville, Nova Scotia, Canada
Abstract. The flow-shop scheduling problem has a long history since Johnson’s seminal paper in 1954, and is still actively studied. The problem is strongly NP-hard when the number of machines is greater than 2. Thus we have to rely on implicit enumeration procedures, such as branch-and-bound, for exact solutions. One of the objectives for researchers in studying such intractable problems is to develop new methods which can solve larger-scale problems. We discuss branch-and-bound algorithms for finding a permutation schedule minimizing the makespan in an mmachine flow shop where the jobs may all be available before processing begins or may be dynamically released. A branch-and-bound algorithm’s performance is helped by sharper lower bounds, good search methods in the tree and more effective dominance relations. Dominance relations are only sufficient but not necessary conditions for optimality, which suggests that optimality may hold with high probability even if a dominance condition is not satisfied exactly, but only approximately. Our algorithms exploit this fact by using a fuzzy approximation of dominance relationships for tie breaking in the search tree and for building initial incumbent schedules. These fuzzy heuristics together with an adaptive branching technique and a generalized decomposition method proved to be very effective for solving large problems. We review the results of large-scale computational experiments for two- and three-machine problems and report on the algorithms’ performance for problems on up to ten machines. The algorithms have proved to be effective in solving a large number of problems with up to several hundred jobs. An interesting byproduct of our research is the rather surprising insight that the difficulty of the problems with release times seems to depend much more on the relative size of the release times than on the number of jobs involved.
1
Introduction
We consider permutation flow shop scheduling problems where the jobs may all be available before processing begins or may be dynamically released. The set J = {1, 2, . . . , n} of n jobs has to be processed without preemption on each of m sequential machines in the same order M1 , M2 , . . . , Mm . Job j has processing time Pl (j) on machine Ml (l = 1, 2, . . . , m). Each job becomes J.-L. Verdegay (ed.), Fuzzy Sets Based Heuristics for Optimization © Springer-Verlag Berlin Heidelberg 2003
22
Jinliang Cheng et al.
available for processing at its release time rj or at the begining of the processing (rj = 0). The objective is to find an optimal sequence for the n jobs so as to minimize the maximum completion time or makespan. According to the traditional notation introduced by Graham et al. [12], the problem can be denoted by F m/rj , perm/Cmax . If all jobs are available at time zero, the corresponding F m/perm/Cmax problem is a classical flow-shop
Data Loading...
