zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. (English) Zbl 1144.90379
Summary: This paper addresses the flexible job shop scheduling problem (fJSP) with three objectives: min makespan, min maximal machine workload and min total workload. We developed a hybrid genetic algorithm (GA) for the problem. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. In order to strengthen the search ability, individuals of GA are first improved by a variable neighborhood descent (VND), which involves two local search procedures: local search of moving one operation and local search of moving two operations. Moving an operation is to delete the operation, find an assignable time interval for it, and allocate it in the assignable interval. We developed an efficient method to find assignable time intervals for the deleted operations based on the concept of earliest and latest event time. The local optima of moving one operation are further improved by moving two operations simultaneously. An extensive computational study on 181 benchmark problems shows the performance of our approach.
MSC:
90B35Scheduling theory, deterministic
68T05Learning and adaptive systems
90C59Approximation methods and heuristics
References:
[1]Gen M, Tsujimura Y, Kubota E. Solving job-shop scheduling problem using genetic algorithms. In: Proceedings of the 16th international conference on computer and industrial engineering, Ashikaga, Japan; 1994. p. 576 – 9.
[2]Brucker, P.; Schlie, R.: Job-shop scheduling with multi-purpose machines, Computing 45, No. 4, 369-375 (1990) · Zbl 0813.90058 · doi:10.1007/BF02238804
[3]Stecke, K. S.: Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems, Management science 29, No. 3, 273-288 (1983) · Zbl 0517.90035 · doi:10.1287/mnsc.29.3.273
[4]Akella, R.; Choong, Y.: Performance of a hierarchical production scheduling policy, IEEE transactions on components, hybrids and manufacturing technology 7, No. 3, 225-248 (1984)
[5]Bona, B.; Brandimarte, P.: Hybrid hierarchical scheduling and control systems in manufacturing, IEEE transactions on robotics and automation 6, No. 6, 673-686 (1990)
[6]Brandimarte, P.: Routing and scheduling in a flexible job shop by tabu search, Annals of operations research 41, 157-183 (1993) · Zbl 0775.90227 · doi:10.1007/BF02023073
[7]Jurisch B. Scheduling jobs in shops with multi-purpose machines. Ph.D. dissertation, Fachbereich Mathematik/Informatik, Universitat Osnabruck; 1992. · Zbl 0863.90087
[8]Hurink, E.; Jurisch, B.; Thole, M.: Tabu search for the job shop scheduling problem with multi-purpose machine, Operations research spektrum 15, 205-215 (1994) · Zbl 0798.90086 · doi:10.1007/BF01719451
[9]Chambers JB. Classical and flexible job shop scheduling by tabu search. Ph.D. dissertation, University of Texas at Austin, USA; 1996.
[10]Dauzère-Pérès, S.; Paulli, J.: An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search, Annals of operations research 70, No. 3, 281-306 (1997) · Zbl 0890.90097 · doi:10.1023/A:1018930406487
[11]Mastrolilli, M.; Gambardella, L. M.: Effective neighborhood functions for the flexible job shop problem, Journal of scheduling 3, No. 1, 3-20 (2000) · Zbl 1028.90018 · doi:10.1002/(SICI)1099-1425(200001/02)3:1<3::AID-JOS32>3.0.CO;2-Y
[12]Yang, J-B.: GA-based discrete dynamic programming approach for scheduling in FMS environments, IEEE transactions on systems, man, and cybernetics — part B 31, No. 5, 824-835 (2001)
[13]Kacem, I.; Hammadi, S.; Borne, P.: Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems, IEEE transaction systems, man, and cybernetics — part C 32, No. 1, 1-13 (2002)
[14]Zhang, H-P.; Gen, M.: Multistage-based genetic algorithm for flexible job-shop scheduling problem, Journal of complexity international 11, 223-232 (2005)
[15]Xia, W.; Wu, Z.: An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problem, Computers & industrial engineering 48, 409-425 (2005)
[16]Wu, Z.; Weng, M-X.: Multiagent scheduling method with earliness and tardiness objectives in flexible job shops, IEEE transactions on system, man, and cybernetics — part B 35, No. 2, 293-301 (2005)
[17]Vaessens RJM. Generalized job shop scheduling: complexity and local search. Ph.D. dissertation, Eindhoven University of Technology; 1995. · Zbl 0841.90079
[18]Brucker, P.; Neyer, J.: Tabu-search for the multi-mode job-shop problem, OR spectrum 20, 21-28 (1998) · Zbl 0897.90122 · doi:10.1007/BF01545525
[19]Baker, K.: Introduction to sequencing and scheduling, (1974)
[20]Gen, M.; Cheng, R.: Genetic algorithms & engineering design, (1997)
[21]Moscato P, Norman M. A memetic approach for the traveling salesman problem: implementation of a computational ecology for combinatorial optimization on message-passing systems. In: Proceedings of the international conference on parallel computing and transputer applications, Amsterdam; 1992.
[22]Gen M, Cheng R. Genetic algorithms amp; engineering optimization. New York: Wiley; 2000. p. 1 – 30.
[23]Mladenovic, N.; Hansen, P.: Variable neighborhood search, Computers & operations research 24, No. 11, 1097-1100 (1997)
[24]Hansen, P.; Mladenovic, N.: Variable neighborhood search: principles and applications, European journal of operational research 130, 449-467 (2001) · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[25]Balas, E.: Machine sequencing via disjunctive graphs: an implicit enumeration algorithm, Operations research 17, 941-957 (1969) · Zbl 0183.49404 · doi:10.1287/opre.17.6.941
[26]Kacem, I.; Hammadi, S.; Borne, P.: Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic, Mathematics and computers in simulation 60, 245-276 (2002) · Zbl 1006.90044 · doi:10.1016/S0378-4754(02)00019-8
[27]Barnes JW, Chambers JB. Flexible job shop scheduling by tabu search. Graduate program in operations research and industrial engineering, The University of Texas at Austin 1996; Technical Report Series: ORP96-09; nbsp;http://ww.cs.utexas.edu/users/jbc/nbsp;.
[28]Fisher H, Thompson GL. Probabilistic learning combinations of local job shop scheduling rules. Englewood Cliffs, NJ: Prentice-Hall; 1963. p. 225 – 51.
[29]Lawrence S. Supplement to resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques. GSIA, Carnegie Mellon University, Pittsburgh, PA; 1984.
[30]Dongarra JJ. Performance of various computers using standard linear equations software. Computer Science Department, University of Tennessee, Knoxville, TN; 2006.
[31]Vaessens, R. J. M.; Aarts, E. H. L.; Lenstra, J. K.: Job shop scheduling by local search, INFORMS journal on computing 8, No. 3, 302-317 (1996) · Zbl 0863.90094 · doi:10.1287/ijoc.8.3.302