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

article

A hybrid approach to large-scale job shop scheduling

Authors:

Cheng WuAuthors Info & Claims

Applied Intelligence, Volume 32, Issue 1

Pages 47 - 59

https://doi.org/10.1007/s10489-008-0134-y

Published: 01 February 2010 Publication History

Abstract

A decomposition based hybrid optimization algorithm is presented for large-scale job shop scheduling problems in which the total weighted tardiness must be minimized. In each iteration, a new subproblem is first defined by a simulated annealing approach and then solved using a genetic algorithm. We construct a fuzzy inference system to calculate the jobs' bottleneck characteristic values which depict the characteristic information in different optimization stages. This information is then utilized to guide the process of subproblem-solving in an immune mechanism in order to promote the optimization efficiency. Numerical computational results show that the proposed algorithm is effective for solving large-scale scheduling problems.

References

[1]

Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manage Sci 34(3):391-401.

[2]

Bassett MH, Pekny JF, Reklaitis GV (1996) Decomposition techniques for the solution of large-scale scheduling problems. AIChE J 42(12):3373-3387.

[3]

Braune R, Wagner S, Affenzeller M (2007) Optimization methods for large-scale production scheduling problems. Lecture notes in computer science, vol 4739. Springer, Berlin, pp 812-819.

[4]

Byeon ES, Wu SD, Storer RH (1998) Decomposition heuristics for robust job-shop scheduling. IEEE Trans Robot Autom 14(2):303- 313.

[5]

Cheng R, Gen M (1996) A tutorial survey of job-shop scheduling problems using genetic algorithms--Part I: representation. Comput Ind Eng 34(4):983-997.

[6]

Cheng R, Gen M (1999) A tutorial survey of job-shop scheduling problems using genetic algorithms--Part II: hybrid genetic search strategies. Comput Ind Eng 36(2):343-364.

Digital Library

[7]

Croce FD, Tadei R, Volta G (1995) A genetic algorithm for the job-shop problem. Comput Oper Res 22(1):15-24.

Digital Library

[8]

Dell'Amico M, Trubian M (1993) Applying tabu search to the job-shop scheduling problem. Ann Oper Res 41(3):231-252.

Digital Library

[9]

Essafi I, Mati Y, Dauzère-Pérès S (2008) A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Comput Oper Res 35(8):2599-2616.

Digital Library

[10]

Jain AS, Meeran S (1999) Deterministic job-shop scheduling: Past, present and future. Eur J Oper Res 113(2):390-434.

[11]

Jang JSR, Sun CT, Mizutani E (1997) Neuro-fuzzy and soft computing. Prentice-Hall, Englewood Cliffs.

[12]

Jiao L, Wang L (2000) A novel genetic algorithm based on immunity. IEEE Tran Syst Man Cybern Part A 30(5):552-561.

Digital Library

[13]

Kolonko M (1999) Some new results on simulated annealing applied to the job shop scheduling problem. Eur J Oper Res 113(1):123-136.

[14]

Laarhoven PJM, Aarts EHL, Lenstra JK (1992) Job shop scheduling by simulated annealing. Oper Res 40(1):113-125.

[15]

Lenstra JK, Kan AHGR, Brucker P (1977) Complexity of machine scheduling problems. Ann Discrete Math 7:343-362.

[16]

Liu M, Hao JH, Wu C (2008) A prediction based iterative decomposition algorithm for scheduling large-scale job shops. Math Comput Model 47(3-4):411-421.

Digital Library

[17]

Luh PB, Gou L, Zhang Y, Nagahora T, Tsuji M, Yoneda K, Hasegawa T, Kyoya Y, Kano T (1998) Job shop scheduling with group-dependent setups, finite buffers and long time horizon. Ann Oper Res 76:233-259.

[18]

Mönch L, Schabacker R, Pabst D, Fowler JW (2007) Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops. Eur J Oper Res 177(3):2100-2118.

[19]

Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manage Sci 42(6):797-813.

[20]

Panwalkar SS, Iskander W (1977) A survey of scheduling rules. Oper Res 25(1):45-61.

Digital Library

[21]

Park MW, Kim YD (1998) A systematic procedure for setting parameters in simulated annealing algorithms. Comput Oper Res 25(3):207-217.

Digital Library

[22]

Singer M (2001) Decomposition methods for large job shops. Comput Oper Res 28(3):193-207.

Digital Library

[23]

Sun D, Batta R (1996) Scheduling larger job shops: a decomposition approach. Int J Prod Res 34(7):2019-2033.

[24]

Tang L, Luh PB, Liu J, Fang L (2002) Steel-making process scheduling using Lagrangian relaxation. Int J Prod Res 40(1):55- 70.

[25]

Vepsalainen AP, Morton TE (1987) Priority rules for job shops with weighted tardy costs. Manage Sci 33(8):95-103.

[26]

Wu SD, Byeon ES, Storer RH (1999) A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness. Oper Res 47(1):113-124.

Digital Library

[27]

Zhang CY, Li PG, Rao YQ, Guan ZL (2008) A very fast TS/SA algorithm for the job shop scheduling problem. Comput Oper Res 35(1):282-294.

Digital Library

[28]

Zhou H, Cheung W, Leung LC (2008) Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. Eur J Oper Res.

Cited By

El-Kholany MSchekotihin KGebser M(2022)Decomposition-Based Job-Shop Scheduling with Constrained ClusteringPractical Aspects of Declarative Languages10.1007/978-3-030-94479-7_11(165-180)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1007/978-3-030-94479-7_11
Gu QLi XJiang SMora H(2019)Hybrid Genetic Grey Wolf Algorithm for Large-Scale Global OptimizationComplexity10.1155/2019/26535122019Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1155/2019/2653512
Chaouch IDriss OGhedira K(2019)A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithmApplied Intelligence10.1007/s10489-018-1343-749:5(1903-1924)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s10489-018-1343-7
Show More Cited By

A hybrid approach to large-scale job shop scheduling
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Minimising makespan for two batch-processing machines with non-identical job sizes in job shop

In this article, the job shop scheduling problem with two batch-processing machines is considered. The machines have limited capacity and the jobs have non-identical job sizes. The jobs are processed in batches and the total size of each batch cannot ...
Tighter bounds on preemptive job shop scheduling with two machines

We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We present an algorithm that finds a schedule of length at most P_max/2 greater than the optimal schedule length, where P_max is the ...
Approximative procedures for no-wait job shop scheduling

In this article we consider the no-wait job shop problem with makespan objective. Based on a decomposition of the problem into a sequencing and a timetabling problem, we propose two local search algorithms. Extensive computational tests in which the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applied Intelligence

Applied Intelligence Volume 32, Issue 1

February 2010

145 pages

ISSN:0924-669X

Issue’s Table of Contents

Copyright © Copyright © 2010 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 February 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

El-Kholany MSchekotihin KGebser M(2022)Decomposition-Based Job-Shop Scheduling with Constrained ClusteringPractical Aspects of Declarative Languages10.1007/978-3-030-94479-7_11(165-180)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1007/978-3-030-94479-7_11
Gu QLi XJiang SMora H(2019)Hybrid Genetic Grey Wolf Algorithm for Large-Scale Global OptimizationComplexity10.1155/2019/26535122019Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1155/2019/2653512
Chaouch IDriss OGhedira K(2019)A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithmApplied Intelligence10.1007/s10489-018-1343-749:5(1903-1924)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s10489-018-1343-7
Sfrent APop F(2015)Asymptotic scheduling for many task computing in Big Data platformsInformation Sciences: an International Journal10.5555/2794084.2794143319:C(71-91)Online publication date: 20-Oct-2015
https://dl.acm.org/doi/10.5555/2794084.2794143
Liu HZhang PHu BMoore P(2015)A novel approach to task assignment in a cooperative multi-agent design systemApplied Intelligence10.1007/s10489-014-0640-z43:1(162-175)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s10489-014-0640-z
Horng SLin SYang F(2012)Evolutionary algorithm for stochastic job shop scheduling with random processing timeExpert Systems with Applications: An International Journal10.1016/j.eswa.2011.09.05039:3(3603-3610)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.eswa.2011.09.050
Tsai J(2012)Solving Japanese nonograms by Taguchi-based genetic algorithmApplied Intelligence10.1007/s10489-011-0335-737:3(405-419)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1007/s10489-011-0335-7

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents