Job Shop Scheduling with Alternative Machines using Genetic Algorithms

Abstract

Sejak kebelakangan ini integrasi fungsi–fungsi pembuatan telah menarik minat sejumlah penyelidik terutamanya dalam perancangan pengeluaran dan penjadualan. Kedua fungsi ini memainkan peranan penting di dalam proses pengeluaran, terutamanya bagi memastikan sumber–sumber pembuatan yang diperlukan untuk melaksanakan proses pengeluaran telah tersedia. Kajian ini telah melihat integrasi penjadualan pengeluaran dengan objektif utamanya ialah menilai keupayaan Algoritma Genetik (GA) dalam menyelesaikan masalah tersebut. Masalah integrasi ini menimbangkan penghalaan alternatif untuk operasi–operasi bagi setiap tugasan semasa pembentukan jadual–jadual. Dalam penghalaan alternatif terdapat pilihan ke atas mesin–mesin yang akan memproses suatu operasi. Mesin–mesin ini mungkin mengambil masa yang berbeza untuk memproses suatu operasi yang sama. Dengan mengambilkira penghalaan alternatif, penyelesaian yang mungkin untuk masalah penjadualan menjadi terlalu besar. Pendekatan GA digunakan bagi mencari penyelesaian terbaik. Pengoptimuman masalah ini melibatkan beberapa objektif, iaitu makespan, kos pemprosesan dan bilangan yang ditolak. Kami telah membandingkan pendekatan yang dicadangkan dengan beberapa pendekatan daripada penyelidik terdahulu dan hasil simulasi telah menunjukkan keputusan yang memuaskan. Kata kunci: Algoritma genetik, penjadualan bengkel kerja, mesin alternatif Recently, an integration of manufacturing functions has gained interest from a number of researchers, particularly in production planning and scheduling. These two functions play important roles in production, especially to ensure the availability of manufacturing resources needed to accomplish production tasks. This paper explores the use of Genetic Algorithms (GA) in solving the problem associated with the integrated production scheduling. The integrated problem considers the alternative routing for operations of each job during the creation of schedules. In alternative routing there is a choice of machines on which to perform the operations. These machines take different amount of time to process the same operation. By considering the alternative routing, the possible solutions for the scheduling problem become very vast. As a robust approach, GA is used to find the most promising solution. The optimization of this problem involves several objectives, namely minimizing makespan, minimizing processing cost, and minimizing number of rejects. It also takes into account the constraints on operations sequence. The proposed solution was compared with previous approaches, and the numerical simulations showed promising results. Key words: Genetic algorithms, job shop scheduling, alternative machines