More Web Proxy on the site http://driver.im/

research-article

Evolutionary algorithm for stochastic job shop scheduling with random processing time

Authors:

Shih-Cheng Horng,

Shieh-Shing Lin,

Feng-Yi YangAuthors Info & Claims

Expert Systems with Applications: An International Journal, Volume 39, Issue 3

Pages 3603 - 3610

https://doi.org/10.1016/j.eswa.2011.09.050

Published: 01 February 2012 Publication History

Abstract

In this paper, an evolutionary algorithm of embedding evolutionary strategy (ES) in ordinal optimization (OO), abbreviated as ESOO, is proposed to solve for a good enough schedule of stochastic job shop scheduling problem (SJSSP) with the objective of minimizing the expected sum of storage expenses and tardiness penalties using limited computation time. First, a rough model using stochastic simulation with short simulation length will be used as a fitness approximation in ES to select N roughly good schedules from search space. Next, starting from the selected N roughly good schedules we proceed with goal softening procedure to search for a good enough schedule. Finally, the proposed ESOO algorithm is applied to a SJSSP comprising 8 jobs on 8 machines with random processing time in truncated normal, uniform, and exponential distributions. The simulation test results obtained by the proposed approach were compared with five typical dispatching rules, and the results demonstrated that the obtaining good enough schedule is successful in the aspects of solution quality and computational efficiency.

References

[1]

Evolution strategies: A comprehensive introduction. Natural Computing. v1 i1. 3-52.

Digital Library

[2]

Complex scheduling. Springer-Verlag, Berlin, Heidelberg.

[3]

. In: Chakraborty, U.K. (Ed.), Computational intelligence in flow shop and job shop scheduling, Springer, Berlin.

Digital Library

[4]

Probability and statistics for engineering and science. 7th ed. Thomson Brooks/Cole, CA.

[5]

Metaheuristics for hard optimization: methods and case studies. Springer-Verlag, Heidelberg, Berlin.

[6]

Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing. v18 i3. 331-342.

[7]

Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop. Journal of Intelligent Manufacturing. v20 i4. 481-498.

[8]

A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem. Computers and Operations Research. v37 i5. 927-937.

Digital Library

[9]

A novel parallel quantum genetic algorithm for stochastic job shop. Journal of Mathematical Analysis and Applications. v355 i1. 63-81.

[10]

Ordinal optimization: Soft optimization for hard problems. Springer-Verlag, New York.

Digital Library

[11]

An ordinal optimization theory based algorithm for a class of simulation optimization problems and application. Expert Systems with Applications. v36 i5. 9340-9349.

Digital Library

[12]

A simulation-optimization approach for integrated sourcing and inventory decisions. Computers and Operations Research. v37 i9. 1648-1661.

Digital Library

[13]

A genetic algorithm for flexible job shop scheduling with fuzzy processing time. International Journal of Production Economics. v48 i10. 2995-3013.

[14]

Simulation-based discrete optimization of stochastic discrete event systems subject to non closed-form constraints. IEEE Transactions on Automatic Control. v54 i12. 2900-2904.

[15]

An empirical study about the usefulness of evolution strategies to solve constrained optimization problems. International Journal of General Systems. v37 i4. 443-473.

[16]

Job shop scheduling by pheromone approach in a dynamic environment. International Journal of Computer Integrated Manufacturing. v23 i5. 412-424.

Digital Library

[17]

Ordinal optimization and quantification of heuristic designs. Discrete Event Dynamic Systems. v19 i3. 317-345.

Digital Library

[18]

Production planning and industrial scheduling: Examples case studies and applications. 2nd ed. PWS Publishing, Boston.

[19]

A hybrid method for solving stochastic job shop scheduling problems. Applied Mathematics and Computation. v170 i1. 185-206.

[20]

Dynamic job shop scheduling using variable neighbourhood search. International Journal of Production Research. v48 i8. 2449-2458.

[21]

A hybrid approach to large-scale job shop scheduling. Applied Intelligence. v32 i1. 47-59.

Digital Library

[22]

Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems. International Journal o Production Research. v47 i11. 2903-2920.

Cited By

Hewa Pathiranage INeumann FAntipov DNeumann ALi XHandl J(2024)Effective 2- and 3-Objective MOEA/D Approaches for the Chance Constrained Knapsack ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654066(187-195)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654066
Ghaedy-Heidary ENejati EGhasemi ATorabi S(2024)A simulation optimization framework to solve Stochastic Flexible Job-Shop Scheduling Problems—CaseComputers and Operations Research10.1016/j.cor.2023.106508163:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.cor.2023.106508
Teck SDewil RVansteenwegen P(2024)A simulation-based genetic algorithm for a semi-automated warehouse scheduling problem with processing time variabilityApplied Soft Computing10.1016/j.asoc.2024.111713160:COnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.111713
Show More Cited By

Evolutionary algorithm for stochastic job shop scheduling with random processing time

Recommendations

Evolutionary Learning Based Simulation Optimization for Stochastic Job Shop Scheduling Problems
Abstract
Simulation Optimization (SO) techniques refer to a set of methods that have been applied to stochastic optimization problems, structured so that the optimizer(s) are integrated with simulation experiments. Although SO techniques ...
Highlights
- A new learning-based simulation Optimization technique named ELBSO is introduced.
Integrating Ant Colony System and Ordinal Optimization for Solving Stochastic Job Shop Scheduling Problem
ISMS '15: Proceedings of the 2015 6th International Conference on Intelligent Systems, Modelling and Simulation

The stochastic job shop scheduling problem (SJSSP) is a kind of stochastic programming problem which transformed from job shop scheduling problem. The SJSSP is an NP-hard problem. Current methods to solve the SJSSP ignored characteristics of SJSSP, ...
Scheduling algorithm for flow shop with two batch-processing machines and arbitrary job sizes

This article considers the problem of scheduling two batch-processing machines in flow shop where the jobs have arbitrary sizes and the machines have limited capacity. The jobs are processed in batches and the total size of jobs in each batch cannot ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Expert Systems with Applications: An International Journal

Expert Systems with Applications: An International Journal Volume 39, Issue 3

February, 2012

1661 pages

ISSN:0957-4174

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 February 2012

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hewa Pathiranage INeumann FAntipov DNeumann ALi XHandl J(2024)Effective 2- and 3-Objective MOEA/D Approaches for the Chance Constrained Knapsack ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654066(187-195)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654066
Ghaedy-Heidary ENejati EGhasemi ATorabi S(2024)A simulation optimization framework to solve Stochastic Flexible Job-Shop Scheduling Problems—CaseComputers and Operations Research10.1016/j.cor.2023.106508163:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.cor.2023.106508
Teck SDewil RVansteenwegen P(2024)A simulation-based genetic algorithm for a semi-automated warehouse scheduling problem with processing time variabilityApplied Soft Computing10.1016/j.asoc.2024.111713160:COnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.111713
Flores-Gómez MBorodin VDauzère-Pérès S(2023)Maximizing the service level on the makespan in the stochastic flexible job-shop scheduling problemComputers and Operations Research10.1016/j.cor.2023.106237157:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.cor.2023.106237
Ghasemi AKabak KHeavey C(2022)Demonstration of the Feasibility of Real Time Application of Machine Learning to Production SchedulingProceedings of the Winter Simulation Conference10.5555/3586210.3586498(3406-3417)Online publication date: 11-Dec-2022
https://dl.acm.org/doi/10.5555/3586210.3586498
Hu RWu XQian BMao JJin H(2022)Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling ProblemComplexity10.1155/2022/99241632022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/9924163
Morady Gohareh MMansouri E(2022)A simulation-optimization framework for generating dynamic dispatching rules for stochastic job shop with earliness and tardiness penaltiesComputers and Operations Research10.1016/j.cor.2021.105650140:COnline publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1016/j.cor.2021.105650
Ghasemi AHeavey C(2021)An evaluation of strategies for job mix selection in job shop production environments - caseProceedings of the Winter Simulation Conference10.5555/3522802.3522923(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3522923
Xie YNeumann ANeumann FSutton AKrawiec K(2021)Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weightsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459381(1187-1194)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459381
Gómez MBorodin VDauzère-Pérès S(2021)A Monte Carlo based method to maximize the service level on the makespan in the stochastic flexible job-shop scheduling problem2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)10.1109/CASE49439.2021.9551529(2072-2077)Online publication date: 23-Aug-2021
https://dl.acm.org/doi/10.1109/CASE49439.2021.9551529
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents