A hybrid optimization algorithm for the job-shop scheduling problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A hybrid optimization algorithm for the job-shop scheduling problem

Full text

Pdf (795 KB)

Source

ACM/SIGEVO Summit on Genetic and Evolutionary Computation archive
Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation table of contents

Shanghai, China

SESSION: Full papers table of contents

Pages 757-764

Year of Publication: 2009

ISBN:978-1-60558-326-6

Authors

Qiang Zhou	Department of Computer Science and Technology, Chuzhou University, Chuzhou, China
Xunxue Cui	New Star Research Institude of Applied Technology, Hefei, China
Zhengshan Wang	Department of Computer Science and Technology, Chuzhou University, Chuzhou, China
Bin Yang	Department of Computer Science and Technology, Chuzhou University, Chuzhou, China

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 42, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1543834.1543938 What is a DOI?

ABSTRACT

The job-shop scheduling problem is a NP-hard combinational optimization and one of the best-known machine scheduling problems. Genetic algorithm is an effective search algorithm to solve this problem; however the quality of the best solution obtained by the algorithm has to improve due to its limitation. The paper proposes a novel hybrid optimization algorithm for the job-shop scheduling problem, which applies chaos theory on the basis of combining genetic programming and genetic algorithm. It improves the quality of the initial population by using chaos optimization method; it maintains the population diversity by chaotic disturbance and anti-equilibration in crossover of genetic programming. Three traversals are adopted to reduce the chance of reaching local optimal solution. Moreover, a scheme of changing weight is proposed during the process of evolution to increase the global exploration capability. The experimental results show that the effectiveness and good quality of the hybrid algorithm is obvious from some benchmarks.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Lageweg B. J., Lenstra J. K., Rinnooy Kan A. H. G. Job-shop scheduling by implicit enumeration. Management Science, 1977, 24:441--450.
	2	Joseph Adams , Egon Balas , Daniel Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science, v.34 n.3, p.391-401, March 1988 [doi>10.1287/mnsc.34.3.391]
	3	Peter J. M. van Laarhoven , Emile H. L. Aarts , Jan Karel Lenstra, Job shop scheduling by simulated annealing, Operations Research, v.40 n.1, p.113-125, Jan.–Feb. 1992 [doi>10.1287/opre.40.1.113]
	4	Mauro Dell'Amico , Marco Trubian, Applying tabu search to the job-shop scheduling problem, Annals of Operations Research, v.41 n.1-4, p.231-252, 1993
	5	T.Yamada, R. Nakano. A genetic algorithm applicable to large-scale job-shop problems. In 2nd PPSN, Proceedings of the 2nd International Workshop on Parallel Problem Solving from Nature, 1992: 281--290.
	6	D.Crafti. 2004 A Job Shop Scheduler using a Genetic Tree Algorithm: in School of Computer Science and Software Engineering. Doctoral Thesis. Melbourne, Australia: Manash University, Clayton Campus, 2004: 63.
	7	Tel Tamas, Gruiz Marton. Chaotic dynamics: An introduction based on classical mechanics. Cambridge University Press, 2006.
	8	Li, T. Y. and Yorke, J. A. Period three implies chaos. Am. Math. Monthly, 1975: 985--992.
	9	Feigenbaum, M.J. Quantitive universality for a class of nonlinear transformations. J. Stat. Phys. 1978, 19: 25--52.
	10	Poli R., Langdon W. B., McPhee N. F. A Field Guide to Genetic Programming, freely available via Lulu.com, 2008.
	11	Marco Tomassini , Leslie Luthi , Mario Giacobini , William B. Langdon, The structure of the genetic programming collaboration network, Genetic Programming and Evolvable Machines, v.8 n.1, p.97-103, March 2007 [doi>10.1007/s10710-006-9018-2]
	12	John R. Koza , David Andre , Forrest H. Bennett , Martin A. Keane, Genetic Programming III: Darwinian Invention & Problem Solving, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
	13	John R. Koza, Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers, Norwell, MA, 2003
	14	Joseph Adams , Egon Balas , Daniel Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science, v.34 n.3, p.391-401, March 1988 [doi>10.1287/mnsc.34.3.391]
	15	Martyn M. T., Zatloukal P.D., Source M. Visualization and Analysis of Interfacial Instability in Coextrusion of LDPE Melt. Plastics, Rubber and Composites, 2004, 33 (1): 27--35.
	16	Vaddiraju S. R., Kostic M., Reifscheider I., et al. Extrusion Simulation and Experimental Validation to Optimize Precision Die Design. ANTEC, 2004, 1:76--80.
	17	Matsunaga K., Kajiwera T., Funatsu K. Numerical Simulation of Multi-layer Flow for Polymer Melts- a Study of the Effect of Viscoelasticity on Interface Shape of Polymers within Dies. Polymer Engineering and Science, 1998, 38(7): 1099--1111.
	18	Rincon A. J., Hrymak A. N., Vlachopoulos J. Transient Finite Element Analysis of Generalized Newtonian Coextrusion Flows in Complex Geometries. International Journal for Numerical Methods in Fluids, 1998, 28(8): 1159--1181.