Open Shop Dense Scheduling Algorithm Based on Semi-Matching Theory

Abstract:

Open shop scheduling problem was studied, and a dense scheduling algorithm based on semi-matching theory was proposed. Using decomposition strategy, the scheduling problem was converted into iterations of resource assignment. Based on this, dense scheduling was constructed by the construction and optimization of primal solution. To improve computational efficiency, the semi-matching model of the resource assignment problem with the optimal function of load balancing was developed. The optimal semi-matching searching algorithm based on augmenting path was proposed. And a dense scheduling construction method with two steps was proposed, as well as initial solution optimization methods and mechanisms to eliminate interference among machines. At last, the validity of the developed scheduling algorithm was illustrated by benchmarks of Taillard.

• Periodical: Key Engineering Materials (Volume 572)
• Pages: 249-252
• DOI: https://doi.org/10.4028/www.scientific.net/KEM.572.249
• Online since: September 2013
• Authors: Yong Zhan, Hai Tao Zhu, Yu Guang Zhong
• Keywords: Dense Scheduling, Open Shop, Resource Assignment, Semi-Matching

References

[1] Matta M E: Computers & Operations Research. September. Vol. 36 (2009), pp.2601-2618.

[2] Gonzalez T, Sahni S: ACM. Vol. 23(1976), pp.665-679.

[3] Brucker P, Hurink J, Jurisch B, Wostmann B: Discrete Applied Mathematics. Vol. 76 (1997), pp.43-59.

[4] Senthilkumar P, Shahbudeen P: International Journal of Advanced Manufacturing Technology. Vol. 30(2006), pp.297-301.

[5] Barany I, Fiala T: Szigma Mathematika Kozgazdasagi Folyoirat. Vol. 17(1982), pp.177-191.

[6] Schuurman P, Woeginger G J: Operations Research Letters. Vol. 24 (1999), pp.157-163.

[7] Harvey N, Ladner R, Lovasz L, Tamir T: Journal of Algorithms. Vol. 59 (2006), pp.53-78.

[8] Taillard E: European Journal of Operational Research. Vol. 64 (1993), pp.278-285.