Solving 5x5 Job-Shop Scheduling Problem Using Genetic Algorithm
Abstract
The job-shop scheduling (JSS) is a production schedule
planning for High mix & low volume systems with many variations in
requirements. They cannot be formulated as a linear programming and
no simple rules or algorithms yield to optimal solutions in a short time.
In job-shop scheduling problem (JSSP) environment, there are n jobs
to be processed on m machines with a certain objective function to be
minimized. JSSP with n jobs to be processed on more than two
machines have been classified as a combinatorial problem. JSSP is
known to be NP-Hard problem and near optimal solution is possible by
heuristics. In this paper, genetic algorithm is used to find the feasible
solution set for 5 x 5 JSSP with total flow time taken as the objective
function. The processing time & job data for the problem is taken from
a glass manufacturing company, which manufactures glass equipment
for pharmaceutical company on received order. Population creation,
encoding, decoding, selection, recombination (crossover), mutation
and reinsertion functions are developed using MATLAB software.
The code is run for various generations and solution set containing
different sequences with same minimum flow time is presented. The
decoding of sequence to schedule is also presented. It is observed that
by operation based representation, decoding of sequence to schedule is
suitable for JSSP.
Keywords
Full Text:
PDFReferences
Baker .K. : introduction to sequencing and scheduling. John wiley & sons,
Newyork,1974
David E Goldberg, Genetic algorithms in search, optimization and
machine learning, pearson education Inc,1989.
C. Bierwirth , D. C. Mattfeld and H. Kopfer. On Permutation
Representations for Scheduling Problems. Parallel Problem Solving from
Nature IV, Springer-Verlag, pp . 310-318 (1996).
G. Mintsuo and C. Runwei.. GA and Engineering Design, John Willey &
Sons Inc, New York USA.(2002).
J. Adams, E. Balas and D. Zawack The Shifting Bottleneck Procedure for
Job Shop Scheduling. Management Science vol.34. (1988).
J.F. Gonçalves, , Jorge José de Magalhães Mendes and M. C. Resende. A
Hybrid Genetic Algorithm for the Job Shop Scheduling Problem..AT&T
Labs Research Technical Report TD- 5EAL6J, September 2002. (2002).
M. Pinedo and X. Chao. Operation Scheduling with Applications in
Manufacturing and Services. McGraw-Hill International Editions.
(1999).
M. T. Jensen and T. K. Hansen. Robust Solutions to Job Shop Problems.
Proceedings of the 1999 Congress on Evolutionary Computation, pages
-1144. (1999).
S. French. Sequencing and Scheduling: An Introduction to the
Mathematics of the Job Shop. John Willey & Sons Inc, New York
USA.(1982).
T. Yamada and R. Nakano. Genetic Algorithms for Job-shop Scheduling
Problems. Proceedings of Modern Heuristic for Decision Support. Pp.
-81, UNICOM Seminar, 18-19 March 1997,London. (1997)
T. Yamada and R. Nakano. Scheduling by Genetic Local Search with
Multi-Step Crossover. The Fourth International Conference on Parallel
Problem Solving from Nature, Berlin, Germany. (1996).
T. Yamada and R. Nakano. A Genetic Algorithm with Multi-Step
Crossover for Job- Shop Scheduling Problems. International Conference
on Genetic Algorithms in Engineering Systems: Innovations and
Application (GALESIA ’95). (1995) .
P.Sureka ,Solution to the Job Shop Scheduling Problem using Hybrid
Genetic Swarm Optimization Based on (λ, 1)-Interval Fuzzy Processing
Time, European Journal of Scientific Research ISSN 1450-216X Vol.64
No.2 (2011), pp. 168-188.
A research paper titled, “Simulated Annealing Algorithm Guided by
Local Search for Minimizing Mean Flow Time in a Job Shop” in the
Industrial Engineering Journal published by The Indian Institution of
Industrial Engineering, Mumbai. Authors: R.K. Suresh and K.M.
Mohanasundaram. VOL. XXXV NO. 3, March 2006.
R.K. Suresh and K.M. Mohanasundaram, “Comparison of Solution
Representation Schemes in Genetic Algorithms for Job Shop
Scheduling”, Proceedings of the International Conference on Intelligent
Flexible Autonomous Manufacturing Systems, TMH Publishing
Company Limited, pp486-494, (2000).
S. Marimuthu, S.G. Ponnambalam and R.K. Suresh, “Evolutionary
algorithm and Threshold accepting algorithm for scheduling in
two-machine flow shop with lot streaming”, Proceedings of the 2004
IEEE Conference Cybernetics and Intelligent Systems (CIS 04), held in
Singapore during 1-3 December 2004
Refbacks
- There are currently no refbacks.