Saturday , April 20 2024

Simulation-based Optimization using Genetic Algorithms
for Multi-objective Flexible JSSP

Elena Simona NICOARA1, Florin Gheorghe FILIP2,3, Nicolae PARASCHIV1
1 Petroleum-Gas University,
39, Bucureşti Blvd., Ploieşti, 100520, Romania,
snicoara@upg-ploiesti.ro
2 Romanian Academy – INCE and BAR,
125 , Calea Victoriei, Bucharest, 010071, Romania
filipf@acad.ro
3 I C I Bucharest
(National Institute for R & D in Informatics)
8-10 Averescu Blvd.
011455 Bucharest 1, Romania

Abstract: The fast technological progress, along with growing requirements in the manufacturing systems have led in the last decades to a true revolution regarding the optimization methods for job shop scheduling problem (JSSP), which regularly has the greatest impact on the global optimality from the temporal perspective. An extension to the mathematical framework associated to the JSSP for multi-objective flexible JSSP (MOFJSSP) is proposed; here, the flexibility of type II, where the routings of the jobs on the resources are not fixed is considered. Also, a short review of the most used simulation-based optimization methods for (MOF)JSSP is made and a genetic algorithm-based control system is proposed. This is then tested on a complex real-world MOFJSS instance and the ft10 test-instance.

Keywords: Multi-objective Flexible Job Shop Scheduling Problem, Simulation-based Optimization, Genetic Algorithm, GA-based Control, NSGA-II.

>>Full text
CITE THIS PAPER AS:
Elena Simona NICOARA, Florin Gheorghe FILIP, Nicolae PARASCHIV, Simulation-based Optimization using Genetic Algorithms for Multi-objective Flexible JSSP, Studies in Informatics and Control, ISSN 1220-1766, vol. 20 (4), pp. 333-344, 2011. https://doi.org/10.24846/v20i4y201101

1. Introduction

Generally speaking, a job shop scheduling problem (JSSP) is a decision-making process for time optimal assignment of some (limited) resources to some heterogeneous jobs consisting in many operations. The resources have to be available and the associated optimization problem is either mono-objective or multi-objective. This kind of scheduling places the problem in the discrete-event systems (DES) domain, whose optimal control often involves computer simulation, at least in the large-scale real-world manufacturing systems.

As shown in [11] the simulation-based optimization can be utilised in the decision-making process for DES. For the specific JSSP case, there are two main aspects which make the decision difficult, namely: a) the constraints can not be explicitly expressed related to the decision variables, and b) the number of the decision alternatives in the search space is huge.

Besides the trivial case when the number of decision alternatives is small to average, where simulation-based optimization consists in evaluating all alternatives to detect the one that provides the best value for the optimization criterion/criteria, the proper meaning of the simulation-based optimization refers to an ordered simulation sequence, determined by an algorithm, applied to different decision parameters until a (near) optimal solution is found [11].

This paper is concerned with simulation-based optimization appropriate to the Multi-objective Flexible JSSP (MOFJSSP). It is organised as follows. An extension of the classical formulation of JSSP to MOFJSSP is presented first. Next, the most used simulation-based optimization methods in the scheduling area are reviewed and a control method, based on a genetic algorithm, is proposed and the test results are presented.

REFERENCES:

  1. BASSEUR, K.M., F. SEYNHAEVE, E. TALBI, Design of Multi-objective Evolutionary Algorithms: Application to the Flow-shop Scheduling Problem, Proc. of the 2002 Congress on Evolutionary Computation (CEC), Hawaii, IEEE Press, vol. 2, 2002, pp. 1151-1156.
  2. BIERWIRTH, C., D. C. MATTFELD, Production Scheduling and Rescheduling with Genetic Algorithms, Evolutionary Computation 7(1), 1999, pp. 1-17.
  1. BRUCKER, P., R. SCHLIE, Job-shop Scheduling with Multi-purpose Machines, Computing 45(4), 1990, pp. 369-375.
  2. CHAN, F. T. S., T. C. WONG, L. Y. CHAN, Flexible Job-Shop Scheduling Problem under Resource Constraints, Intl. J. of Production Research 44(11), 2006, pp. 2071-2089.
  3. 5. CHENG, R. W, M. GEN, Y. TSUJIMURA, A Tutorial Survey of Job Shop Scheduling Problems using Genetic Algorithms: Part II: Hybrid Genetic Search Strategies, Intl. J. of Computers and Industrial Engineering 36, 1999, pp.343-364.
  4. DAVIS, L., Job Shop Scheduling with Genetic Algorithms, Proc. of the Intl. Conference on Genetic Algorithms and their Applications, San Mateo, Morgan Kaufmann, 1985, pp. 136-149.
  5. DEB, K., S. AGRAWAL, A. PRATAP, T. MEYARIVAN, A Fast and Elitist Multi-objective Genetic Algorithm for Multi-objective Optimization: NSGA-II, Proc. of VI-th Parallel Problem Solving from Nature Conference, Paris, 2000, pp. 849-858.
  6. DOLGUI, A., J.-M. PROTH, Supply Chain Engineering: Useful Methods and Techniques, Springer-Verlag, London, 2010.
  7. DUŢĂ, L., F. G. FILIP, J. M. HENRIOUD, C. POPESCU, Disassembly Line Scheduling with Genetic Algorithms, Int. J. of Computer Communication and Control, 3(3) , 2008, pp. 270-280
  8. FILIP, F. G., Contributions to Hierarchical Control of Complex Systems, Ph.D. Thesis, Polytechnic Institute of Bucharest, Romania, 1981 (in Romanian).
  9. FILIP, F. G., Decizie Asistată de Calculator: Decizii, Decidenţi – Metode de Bază şi Instrumente Informatice Asociate (“Computer Aided Decision making; Methods and Associated Information Tools”). second edition, Ed. Tehnică, Bucureşti, 2005 (in Romanian)
  10. FILIP, F. G., G. NEAGU, D. A. DONCIULESCU, Job Shop Scheduling Optimization in Real-time Production Control, Computers in Industry 4, Elsevier, 1983, pp. 395-403.
  11. FISHER, H., G. L. THOMPSON, Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules, Industrial Scheduling, J. F. Muth & G. L. Thompson (Eds.), Prentice-Hall, Englewood Cliffs, NJ. French, 1963, pp. 225-251.
  12. FRENCH, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, Chichester, England, Ellis Horwood Ltd., 1982.
  13. GIFFLER, B., G. L. THOMPSON, Algorithms for Solving Production Scheduling Problems, Operations Research 8(4), 1960, pp. 487-503.
  14. GREFENSTETTE, J. J., Incorporating Problem Specific Knowledge into Genetic Algorithms, in L. Davis (Ed.) Genetic Algorithms and Simulated Annealing, Morgan Kaufmann , 1987, pp. 42-60.
  15. HOLLAND, J. H., Genetic Algorithms, Scientific American 267(1), 1992, pp. 44-50.
  16. JAIN, A. S., S. MEERAN, Deterministic Job Shop Scheduling: Past, Present and Future, European Journal of Operational Research 113(2), 1998.
  17. JAIN, A. S., S. MEERAN, A State-of-the-Art Review of Job-Shop Scheduling Techniques, European Journal of Operations Research 113, 1999, pp. 390-434.
  18. JONES, A., L. C. RABELO, Survey of Job-Shop Scheduling Techniques, M. Sc. dissertation, NISTIR, Gaithersburg, MSID Publications, 1998.
  19. KAUFMANN, M., Methods and Models of Operations Research, vol. II, Ed. Ştiinţifică şi Enciclopedică, Bucureşti, 1975 (in Romanian).
  20. MCGOVERN, S. M., S. M. GUPTA, The Disassembly Line: Balancing and Modeling, McGraw-Hill, New York, 2011.
  21. NICOARĂ, E. S., Mechanisms to Avoid the Premature Convergence of Genetic Algorithms, Petroleum – Gas University of Ploieşti Bulletin, Math. – Info. – Phys. Series, vol. LXI, 1/2009, pp.87-96.
  22. NICOARĂ, E. S, GA-based Control of Multi-objective Flexible Job Shop Scheduling Processes, Ph.D. Thesis, Petroleum-Gas University of Ploieşti, 2011 (in Romanian).
  23. PINEDO, M. L., Scheduling. Theory, Algorithms, and Systems, 3rd ed., Springer, New York, 2008
  24. WOLPERT, D. H., W. G. MACREADY, No Free Lunch Theorems for Optimization, IEEE Trans. on Evolutionary Computation 1(1), 1997, pp. 67-82.
Designed by | ICI Bucharest
© Copyright 2024, All Rights Reserved