Application of mixed integer linear programming in optimization of sequence-dependent fluid packaging production scheduling

In the manufacturing process of packaging fluid, there are processes in between the assigned producing jobs called ‘changeover’ in which the machine or the production line must have an adjustment to prepare for the upcoming job. Therefore, scheduling requires optimization to minimize the total production time from the changeover of the sequence scheduled. The process is normally executed by a planner with effort spent to find the optimal solution with the lowest makespan as fast as possible. This research considers the job scheduling problem with sequence-dependent changeover times on a single machine to minimize the makespan of the jobs assigned. Different changeover types with varied required times will be assumed. To provide an effort improvement tool, a mixed integer linear programming (MILP) is developed to compute the optimal solution and compared with the human-executed heuristic proposed to find the solution with a better computational time in exchange for a non-optimized solution. Up to 71 jobs, the developed MILP with a tolerance 0.5% takes approximately 60 minutes to find the solution. In comparison, the heuristic cannot reduce the computational time until scheduling 71 jobs and can reduce the computational time by 87.5%. However, compared to the MILP with a tolerance of 5%, it can reduce the computational time and the MILP with a tolerance of 0.5% and can improve the results compared to the heuristic at any number of jobs.