Comparison of Different Approaches to the Cutting Plan Scheduling

Peter Bober

Abstract

Allocation of specific cutting plans and their scheduling to individual cutting machines presents a combinatorial optimization problem. In this respect, various approaches and methods are used to arrive to a viable solution. The paper reports three approaches represented by three discreet optimization methods. The first one is back-tracing algorithm and serves as a reference to verify functionality of the other two ones. The second method is optimization using genetic algorithms, and the third one presents heuristic approach to optimization based on anticipated properties of an optimal solution. Research results indicate that genetic algorithms are demanding to calculate though not dependant on the selected objective function. Heuristic algorithm is fast but dependant upon anticipated properties of the optimal solution. Hence, at change of the objective function it has to be changed. When the scheduling by genetic algorithms is solvable in a sufficiently short period of time, it is more appropriate from the practical point than the heuristic algorithm. The back-tracing algorithm usually does not provide a result in a feasible period of time.

References

Bober, P (2007), “Optimization of cutting plans for more machines by searching of solution tree”, Journal “Quality Innovation Prosperity”, vol. 11, no. 2, p. 9-17 (In Slovak).

Bober, P (2008), “Optimization of Cutting Plans Using Genetic Algorithms”, Journal “Quality Innovation Prosperity”, vol. 12, no. 2, p. 1-10, (In Slovak).

Bubeník, P. (2004), “A scheduling system for minimizing the cost of productions”, Strojniški Vestnik - Journal of Mechanical Engineering, vol. 50, no. 5, ISSN 0039-2480, p. 291-297.

Cal'egaria P., Guideca, F., Kuonena, P., Nielsen, F. (2001), “Combinatorial optimization algorithms for radio network planning”, Theoretical Computer Science 263, p. 235–245.

Dhaenens, C., Lemesre, J., Talbi, E.G. (2010), “K-PPM: A new exact method to solve multi-objective combinatorial optimization problems”, European Journal of Operational Research, vol. 200, no. 1, p. 45-53, doi:10.1016/j.ejor.2008.12.034.

Duque, T., Goldberg, D. E., Sastry, K. (2008), “Enhancing the Efficiency of the ECGA”, TR No. 2008006, Retrieved on 3.11.2010 from http://www.illigal.uiuc.edu/pub/papers/IlliGALs/2008006.pdf.

Fabian, M., Spišák, E., Šeminský, J., Dovica, M. (2009), “Anticipation of Cutting Surface Quality from Pre-Set CAM Parameters”, Ovidius University Annual Scientific Journal, vol. 11, no. 1, p. 19-24.

Goldberg, D. E. (1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, ISBN 0-201-15767-5.

Golomb, S. W., Baumert, L. D. (1965), “Backtrack Programming”, Jornal of the. ACM, vol. 12, no. 4, p. 516-524, DOI: 10.1145/321296.321300.

Grossmann, I. E., Heever, S. A., Harjunkoski, I. (2002), “Discrete Optimization Methods and their Role in the Integration of Planning and Scheduling”, AIChE Symposium Series, no. 326, vol. 98, p. 150-168.

Gutin, G., Vainshtein, A., Yeo, A. (2003), “Domination analysis of combinatorial optimization problems”. Discrete Applied Mathematics, vol. 129, no. 2-3, p. 513-520, DOI: 10.1016/S0166-218X(03)00359-7.

Hua, Q-S., Wang, Y., Yu, D., Lau, F. C. M. (2010), “Dynamic programming based algorithms for set multicover and multiset multicover problems”. Theoretical Computer Science, vol. 411, no. 26-28, p. 2467-2474, DOI: 10.1016/j.tcs.2010.02.016.

Jaszkiewicz, A. (2002), “Genetic local search for multi-objective combinatorial optimization”, European Journal of Operational Research, vol. 137, no. 1, p. 50-71, DOI: 10.1016/S0377-2217(01)00104-7.

Pentico, D. W. (2007), “Assignment problems: A golden anniversary survey”, European Journal of Operational Research, vol. 176, no. 2, p, 774-792, DOI: 10.1016/j.eor.2005.09.014.

Rajagopalan, S., Vazirani, V. V. (1993), “Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs”. In SFCS '93 Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, Washington, DC, p. 322 – 331, DOI: 10.1109/SFCS.1993.366855.

Sergienko, I. V., Hulianytskyi, L. F., Sirenko, S. I. (2009), “Classification of applied methods of combinatorial optimization”, Cybernetics and Systems Analysis, vol. 45, no. 5, p. 732-741.

Slak, A., Tav?ar, J., Duhovnik, J. (2011), “Application of Genetic Algorithm into Multicriteria Batch Manufacturing Scheduling”, Strojniški vestnik - Journal of Mechanical Engineering, vol. 57, no. 2, p. 110-124, DOI:10.5545/sv-jme.2010.122.

Teghem, J., Tuyttens, D., Ulungu, E. L. (2000), “An interactive heuristic method for multi-objective combinatorial optimization”, Computers & Operations Research, vol. 27, no. 7-8, p. 621-634, DOI: 10.1016/S0305-0548(99)00109-4.

Zalzala, A. M. S., Fleming, P. J. (editors) (1997), Genetic algorithms in engineering systems, London: Institution of Electrical Engineers, ISBN 0 85296 902 3.

Zhang, H., Ishikawa, M. (2004), “A solution to combinatorial optimization with time-varying parameters by a hybrid genetic algorithm”, in International Congress Series, vol. 1269, Brain-Inspired IT I. Invited papers of the 1st Meeting entitled Brain IT 2004, August 2004, p. 149-152, DOI: 10.1016/j.ics.2004.05.019.

Authors

Peter Bober
peter.bober@tuke.sk (Primary Contact)
Bober, P. (2011). Comparison of Different Approaches to the Cutting Plan Scheduling. Quality Innovation Prosperity, 15(1), 47–56. https://doi.org/10.12776/qip.v15i1.35
Copyright and license info is not available

Article Details

MEDICAL STAFF SCHEDULING USING SIMULATED ANNEALING

Ladislav Rosocha, Silvia Vernerova, Robert Verner
Abstract View : 1895
Download :1635