Penerapan Algoritma Branch and Bound dalam Menyelesaikan Penjadwalan Flowshop

Abstract

Penjadwalan adalah pengalokasian sumber daya atau mesin untuk menyelesaikan serangkaian tugas dalam batas waktu yang ditentukan. Tugas-tugas tersebut, yang juga dikenal sebagai job, merupakan operasi yang dilakukan dalam proses produksi. Penjadwalan dilakukan dengan tujuan meminimalkan biaya total dan menyelesaikan pesanan tepat waktu. Selain itu, penjadwalan juga bertujuan untuk mengurangi persediaan barang setengah jadi dan menghindari pekerjaan yang tidak efisien, serta membantu dalam pengambilan keputusan terkait perencanaan kapasitas pabrik. Keputusan penjadwalan melibatkan pengurutan pekerjaan, penentuan waktu mulai dan selesai, serta urutan proses. Kesalahan dalam menentukan prioritas pekerjaan dapat menyebabkan waktu produksi yang tinggi. PT. X mengalami masalah keterlambatan penyelesaian pesanan yang menyebabkan ketidakmampuan memenuhi permintaan konsumen. Metode yang digunakan perusahaan saat ini adalah First Come First Serve (FCFS) dalam menjadwalkan job. Job dikerjakan berdasarkan urutan kedatangan, yaitu job 1 - job 2 - job 3 - job 4 dengan total makespan 200 jam. Oleh karena itu, dilakukan penjadwalan menggunakan Algoritma Branch and Bound untuk meminimalkan makespan. Metode Branch and Bound adalah pendekatan yang memberikan solusi terbaik berdasarkan kriteria tertentu dengan tingkat kesalahan yang lebih rendah dibandingkan metode heuristik lainnya. Hasilnya menunjukkan bahwa penjadwalan dengan Algoritma Branch and Bound menghasilkan makespan terpendek.

Resources or machines that are allocated in the implementation of a set of tasks within a certain period of time is called scheduling. Scheduling involves working on a number of components which are often called Jobs. Job is a basic element that can be called an activity or operation. The goal of scheduling is to complete orders on time and minimize total costs. In addition, scheduling also aims to reduce inventories of semi-finished goods or reduce a number of other work tasks and assist in making decisions regarding planning factory capacity and the type of capacity needed so that excessive additional costs can be avoided. Decision-making in scheduling includes sequencing, start and finish times (timing), and the sequence of processes of a job (routing). A high total production time value will arise as a result of using the wrong job priority order. The problems that occurred at PT. Cakra Compact Aluminum Industries is still experiencing delays in completing orders to meet consumer demand. The company has been using the First Come First Serve (FCFS) method in scheduling every incoming job. The sequence of jobs carried out based on the job that arrives first is job 1 - job 2 - job 3 - job 4 with a total makespan of 200 hours. Then do the scheduling with the Branch and Bound Algorithm to minimize makespan time. The Branch and Bound method is an approach that provides the best solution to a problem in terms of certain criteria and has a lower error rate compared to other heuristic methods. It is found that scheduling with  Branch and Bound algorithm produces the shortest makespan, namely 177.66 hours with job order 1-4-3-2.