A genetic algorithm for job shop scheduling with load balancing
Pages 339 - 348
Abstract
This paper deals with the load-balancing of machines in a real-world job-shop scheduling problem with identical machines. The load-balancing algorithm allocates jobs, split into lots, on identical machines, with objectives to reduce job total throughput time and to improve machine utilization. A genetic algorithm is developed, whose fitness function evaluates the load-balancing in the generated schedule. This load-balancing algorithm is used within a multi-objective genetic algorithm, which minimizes average tardiness, number of tardy jobs, setup times, idle times of machines and throughput times of jobs. The performance of the algorithm is evaluated using real-world data and compared to the results obtained with no load-balancing.
References
[1]
Fayad, C. and Petrovic, S., "A Genetic Algorithm for Real-World Job Shop Scheduling", in Ali, M. and Esposito, M., (Eds.), Innovations in Applied Artificial Intelligence, LNAI-3533, the 18th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 22-25 June, Bari, Italy. 2005.
[2]
Greene, W., "Dynamic Load-Balancing via a Genetic Algorithm," 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'01), Dallas, US, (2001) 121-129.
[3]
Kranzlmuller, D., 'Scheduling and Load Balancing,' Fifth International Conference on Parallel Processing and Applied Mathematics, Czestochowa, Poland, LNCS-3019, Springer Verlag, (2003).
[4]
Lee, S. and Lee, D., "GA based adaptive load balancing approach for a distributed system", in Zhang, J. and He J-H; Fu Y. (Eds), Computational and Information Science, Kralov, Poland, LNCS 3314, Springer-Verlag, (2004) 182-7.
[5]
Moon, D.H., Kim, D.K. and Jung J.Y., An Operator Load-Balancing problem in a Semi-Automatic Parallel Machine Shop, Computers & Industrial Engineering 46 (2004) 355-362.
[6]
Petrovic S., Fayad C. and Petrovic D., "Job Shop Scheduling with Lot-Sizing and Batching in an Uncertain Real-World Environment," 2nd Multidisciplinary Conference on Scheduling: Theory and Applications (MISTA), 18-21 July, NY, USA (2005).
[7]
Pinedo, M., Scheduling Theory, Algorithms, and Systems, Prentice Hall, Second Edition, (2002).
[8]
Reeves, C., Genetic Algorithms and Combinatorial Optimisation: Applications of Modern Heuristic Techniques, In V.J. Rayward-Smith (Eds), Alfred Waller Ltd, Henley-on-Thames, UK (2005).
[9]
Zomaya, A. and Teh, Y.H., Observations on Using Genetic Algorithms for Dynamic Load-Balancing, IEEE Transactions on Parallel and Distributed Systems, 12 9 (2001) 899-911.
[10]
Wang, T and Fu Y., "Application of An Improved Genetic Algorithm for Shop Floor Scheduling," Computer Integrated Manufacturing Systems, 8 5 (2002) 392-420.
Recommendations
A fuzzy genetic algorithm for real-world job shop scheduling
IEA/AIE'2005: Proceedings of the 18th international conference on Innovations in Applied Artificial IntelligenceIn this paper, a multi-objective genetic algorithm is proposed to deal with a real-world fuzzy job shop scheduling problem. Fuzzy sets are used to model uncertain due dates and processing times of jobs. The objectives considered are average tardiness ...
Heuristic Optimization for Dual-resource Constrained Job Shop Scheduling
CAR '09: Proceedings of the 2009 International Asia Conference on Informatics in Control, Automation and RoboticsIn the study of job shop scheduling problem in mass injection molding processing enterprises, the practical job shop scheduling environment cannot be mirrored in the traditional study only considering machine resources. A dual-resource (machines and ...
Multi-criteria sequence-dependent job shop scheduling using genetic algorithms
Real world job shops have to contend with jobs due on different days, material ready times that vary, reentrant workflows and sequence-dependent setup times. The problem is even more complex because businesses often judge solution goodness according to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- University of Technology, Sydney: University of Technology, Sydney
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 05 December 2005
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025