A PMBGA to optimize the selection of rules for job shop scheduling based on the Giffler-Thompson algorithm
type: Item
instance of: scholarly article
title: A PMBGA to optimize the selection of rules for job shop scheduling based on the Giffler-Thompson algorithm
zbMATH Open document ID: 1235.90069
DOI: 10.1155/2012/623230
author: Cheng Wu
author: Rui Zhang
published in: Journal of Applied Mathematics
publication date: 2012-04-04T00:00:00Z
review text: Summary: Most existing research on the job shop scheduling problem has been focused on the minimization of makespan (i.e., the completion time of the last job). However, in the fiercely competitive market nowadays, delivery punctuality is more important for maintaining a high service reputation. So in this paper, we aim at solving job shop scheduling problems with the total weighted tardiness objective. Several dispatching rules are adopted in the Giffler-Thompson algorithm for constructing active schedules. It is noticeable that the rule selections for scheduling consecutive operations are not mutually independent but actually interrelated. Under such circumstances, a probabilistic model-building genetic algorithm (PMBGA) is proposed to optimize the sequence of selected rules. First, we use Bayesian networks to model the distribution characteristics of high-quality solutions in the population. Then, the new generation of individuals is produced by sampling the established Bayesian network. Finally, some elitist individuals are further improved by a special local search module based on parameter perturbation. The superiority of the proposed approach is verified by extensive computational experiments and comparisons.
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 6021720
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2012/623230
OpenAlex ID: W1995918244
Wikidata QID: Q58906256
cites work: Q4124328
cites work: A general approach for optimizing regular criteria in the job-shop scheduling problem
cites work: An improved genetic algorithm for the distributed and flexible job-shop scheduling problem
cites work: Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times
cites work: An advanced tabu search algorithm for the job shop problem
cites work: Ant colony optimisation with parameterised search space for the job shop scheduling problem
cites work: Scheduling
cites work: Q4238569
cites work: A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops
cites work: Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops
cites work: A large step random walk for minimizing total weighted tardiness in a job shop
cites work: Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm
cites work: A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem
cites work: Minimizing total weighted tardiness in a generalized job shop
cites work: Improving job shop performance by coordinating dispatching rules
cites work: A new dispatching rule based genetic algorithm for the multi-objective job shop problem
cites work: Deterministic job-shop scheduling: Past, present and future
cites work: Learning Bayesian networks: The combination of knowledge and statistical data
cites work: A survey of optimization by building and using probabilistic models
cites work: Towards a new evolutionary computation. Advances on estimation of distribution algorithms.
cites work: An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems
DBLP publication ID: journals/jam/ZhangW12a
Recommended article: An algorithm for the job shop scheduling problem based on global equilibrium search techniques
Recommended article: A priority-based genetic algorithm for a flexible job shop scheduling problem
Recommended article: A general approach for optimizing regular criteria in the job-shop scheduling problem
Recommended article: Evolutionary Computation in Combinatorial Optimization
Recommended article: An tentative taboo search algorithm for job shop scheduling
Recommended article: A PARTICLE SWARM OPTIMIZATION-BASED ALGORITHM FOR JOB-SHOP SCHEDULING PROBLEMS
Recommended article: Instance space analysis and algorithm selection for the job shop scheduling problem
Recommended article: Q5320080
description: scientific article; zbMATH DE number 6021720