Research on Open Shop Scheduling Based on Genetic Algorithm

Yong Zhan; Yu Guang Zhong; Hai Tao Zhu

doi:10.4028/www.scientific.net/AMR.655-657.1670

Paper Titles

The Resource Conflicts Detecting Method of Virtual Manufacturing Cell Based on Bayesian Network
p.1650

Three Dimensional Assembly Tolerance Analysis of Gear Drivetrain
p.1656

Reach on the Application of Digital Factory Technology in Process Planning and Line Teaching Field of Automobile Manufacture
p.1662

Reach on the Buffer Capacity Design between Body Shop Lines of Aar with Simulation Analysis
p.1666

Research on Open Shop Scheduling Based on Genetic Algorithm
p.1670

A Modified Genetic Algorithm for Sequencing Problem in Mixed Model Assembly Lines
p.1675

Computer-Aided Production Control of Automobile Injection Molds Based on Process Perception
p.1682

Research and Application of the Visual Assembly System Based on the Process Lightweight Model
p.1687

Cubic Polynomial Trajectory Planning Algorithm Based on Ideal Drive Force for Aircraft Fusagle Automatic Position and Pose Adjustment
p.1691

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 655-657Research on Open Shop Scheduling Based on Genetic...

Research on Open Shop Scheduling Based on Genetic Algorithm

Abstract:

Open shop scheduling problem is a typical NP problem with wide engineering background. It is of importance with respect of theory and application. In this paper, a mixed integer programming model was established with the objective to minimize the makespan based on the characteristics of the open shop, and a evolution genetic algorithm(EGA) was proposed. The representation of chromosome used in this paper was composed of two layers: operation layer and machine layer, which can be encoded and decoded easily. In generating initial population, DS/LTRP heuristic was used in order to improve the quality of the population. And particular crossover operation was proposed, which generated multiple offspring at a time, so that the efficiency of the algorithm can be well improved. At last, the proposed algorithm was tested on taillard benchmark, and numerical example showed good result.

You might also be interested in these eBooks

Engineering Solutions for Manufacturing Processes

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 655-657)

Pages:

1670-1674

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.655-657.1670

Citation:

Cite this paper

Online since:

January 2013

Authors:

Yong Zhan, Yu Guang Zhong, Hai Tao Zhu

Keywords:

Genetic Algorithm (GA), Open Shop, Resource Constraints

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Han B, Xi Y G. Schedule methodology of approximate optimal cost of total time and makespan for muti-machines in open shop. Control Theory and Application. Vol. 20(6)( 2003), pp.859-864.

Google Scholar

[2] Matta M E. A genetic algorithm for the proportionate multiprocessor open shop. Computers & Operations Research. Vol. 36(9)( 2009), pp.2601-2618.

DOI: 10.1016/j.cor.2008.11.009

Google Scholar

[3] Gonzalez T, Sahni S. Open shop scheduling to minimize finish time. ACM. Vol. 23(1976), pp.665-679.

DOI: 10.1145/321978.321985

Google Scholar

[4] Brucker P, Hurink J, Jurisch B, Wostmann B. A branch & bound algorithm for the open-shop problem. Discrete Applied Mathematics. Vol. 76(1997), pp.43-59.

DOI: 10.1016/s0166-218x(96)00116-3

Google Scholar

[5] Ulrich D, Erwin P, Toàn P H. Solving the open shop scheduling problem. Journal of Scheduling. Vol. 4(3)( 2001), pp.157-174.

Google Scholar

[6] Laborie P. Complete mes-based search: Application to resource constrained project scheduling. International Joint Conference on Artificial Intelligence(2005), pp.181-186.

Google Scholar

[7] Liaw C F. An iterative improvement approach for the nonpreemptive open shop scheduling problem. European Journal of Operational Research. Vol. 111(1998), pp.509-517.

DOI: 10.1016/s0377-2217(97)00366-4

Google Scholar

[8] Susana C. Esquivel, Federico Zuppa, Raul H. Multirecombinated Evolutionary Algorithms for the Flow Shop Scheduling Problem. Lecture Notes In Computer Science. Vol. 1917(2000), pp.263-272.

DOI: 10.1007/3-540-45356-3_26

Google Scholar

[9] Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research. Vol. 64(1993), pp.278-285.

DOI: 10.1016/0377-2217(93)90182-m

Google Scholar