Optimisasi Penyusunan Jadwal Menggunakan Pendekatan Pembangkit Kolom (Column Generation)

Abstract

Abstract –  Scheduling problem can be modeled by using linear integer programming and completed using the column generation method. Column generation methods taking sub-set of the set of large columns to be resolved. This new column is generated when variables corresponding to that column potentially optimize the purpose function. The purpose of this research is to model integer program for scheduling, forming process with column generation approach, and get optimization result from scheduling. This research is the oretical research. Which is a literature study based on the relevant sources. Based on the result, obtained model scheduling problem in the form of linear integer program, the scheduling model is processed by the column generation method, that is Master Problem formation, Restricted Master Problem, then RMP is formed dual so tested using pricing problem until got optimal result. The method was applied to the sample in order to get the most optimal schedule.