Open Access Open Access  Restricted Access Subscription or Fee Access

Solving 5x5 Job-Shop Scheduling Problem Using Genetic Algorithm

A.L. Kameswari, Dr. K. Sreenivasa Rao

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


Evolutionary Algorithms - EA, Genetic Algorithm- GA, Job Shop Scheduling Problem -JSSP, Non Polynomial Time -NP, Partially Mapped Crossover - PMX.

Full Text:

PDF

References


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.