A Branch and Bound and Simulated Annealing Approach for Job Shop Scheduling

Abstract

Kertas ini membincangkan dua penyelesaian untuk menyelesaikan masalah penjadualan bengkel kerja iaitu kaedah cabang dan batas serta kaedah simulasi penye\-puhlindapan. Objektifnya adalah untuk menjadualkan kerja-kerja kepada mesin-mesin supaya jumlah masa penyelesaian adalah minimum. Dalam kaedah cabang dan batas, masalah penjadualan bengkel kerja telah diwakili oleh graf disjungtif, selepas itu, jadual optima boleh didapati dengan menggunakan algoritma cabang dan batas manakala simulasi penyepuhlindapan merupakan algoritma pencarian tempatan yang akan membuat usikan kecil kepada penyelesaian awal tersaur untuk mengurangkan ``makespan.'' Katakunci: Penjadualan bengkel kerja; cabang dan batas; formulasi graf disjungtif; simulasi penyepuhlindapan. This paper presents two approaches to the solution of the job shop scheduling problem, namely the branch and bound, and simulated annealing approach. The objective is to schedule the jobs on the machines so that the total completion time is minimized. In the branch and bound approach, the job shop scheduling problem is represented by a disjunctive graph, then the optimal schedule is obtained using the branch and bound algorithm while simulated annealing is a local search based algorithm which will slightly perturb the initial feasible solution to decrease the makespan. Keywords: Job shop scheduling; branch and bound; disjunctive graph formulation; simulated annealing.