Optimal computing budget allocation for ordinal optimization in solving stochastic job shop scheduling problems
type: Item
instance of: scholarly article
title: Optimal computing budget allocation for ordinal optimization in solving stochastic job shop scheduling problems
zbMATH Open document ID: 1407.90195
DOI: 10.1155/2014/619254
author: Hong-an Yang
author: Yangyang Lv
author: Changkai Xia
author: Honghao Wang
author: Shudong Sun
published in: Mathematical Problems in Engineering
publication date: 2019-02-08T00:00:00Z
review text: Summary: We focus on solving Stochastic Job Shop Scheduling Problem (SJSSP) with random processing time to minimize the expected sum of earliness and tardiness costs of all jobs. To further enhance the efficiency of the simulation optimization technique of embedding Evolutionary Strategy in Ordinal Optimization (ESOO) which is based on Monte Carlo simulation, we embed Optimal Computing Budget Allocation (OCBA) technique into the exploration stage of ESOO to optimize the performance evaluation process by controlling the allocation of simulation times. However, while pursuing a good set of schedules, ``super individuals,'' which can absorb most of the given computation while others hardly get any simulation budget, may emerge according to the allocating equation of OCBA. Consequently, the schedules cannot be evaluated exactly, and thus the probability of correct selection (PCS) tends to be low. Therefore, we modify OCBA to balance the computation allocation: (1) set a threshold of simulation times to detect ``super individuals'' and (2) follow an exclusion mechanism to marginalize them. Finally, the proposed approach is applied to an SJSSP comprising 8 jobs on 8 machines with random processing time in truncated normal, uniform, and exponential distributions, respectively. The results demonstrate that our method outperforms the ESOO method by achieving better solutions.
Mathematics Subject Classification ID: 90B36
Mathematics Subject Classification ID: 90C15
zbMATH DE Number: 7016874
Wikidata QID: Q59066614
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2014/619254
OpenAlex ID: W2041942729
cites work: Interval scheduling: A survey
cites work: A genetic algorithm for flexible job shop scheduling with fuzzy processing time
cites work: Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms
cites work: A fuzzy robust scheduling approach for product development projects.
cites work: Q3624051
cites work: A novel parallel quantum genetic algorithm for stochastic job shop scheduling
cites work: A genetic algorithm and the Monte Carlo method for stochastic job-shop scheduling
cites work: Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems
cites work: A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem
cites work: Dynamic job shop scheduling using variable neighbourhood search
cites work: An artificial bee colony algorithm for the job shop scheduling problem with random processing times
cites work: Ordinal Optimization
cites work: Simulation budget allocation for further enhancing the efficiency of ordinal optimization
cites work: Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems
cites work: Dynamics and convergence rate of ordinal comparison of stochastic discrete-event systems
cites work: Explanation of goal softening in ordinal optimization
cites work: Evolution strategies. A comprehensive introduction
cites work: A new approach to discrete stochastic optimization problems
Recommended article: Ordinal optimization with computing budget allocation for selecting an optimal subset
Recommended article: Efficient Computing Budget Allocation for Simulation-Based Optimization With Stochastic Simulation Time
Recommended article: Computing efforts allocation for ordinal optimization and discrete event simulation
Recommended article: Multi-stage ordinal optimization based approach for job shop scheduling problems
Recommended article: A new approach to computing optimal schedules for the job-shop scheduling problem
Recommended article: Ordinal optimization based approach to the optimal resource allocation of grid computing system
Recommended article: On the Structure of Optimal Greedy Computation (for Job Scheduling)
Recommended article: Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system
description: scientific article; zbMATH DE number 7016874