A SCHEDULING HEURISTIC FOR A CONVEYOR BELTING TWO-STAGE UNIFORM MACHINES HYBRID FLOW SHOP

Abstract

Most production planning focuses on allocating resources to jobs in unoptimised schedules. In this work, a bi-weekly job scheduling ensemble of heuristics for optimising makespan is developed for a two-stage Hybrid-Flow-Shop (HFS) with two similar machines in the first and four similar machines in the second. The HFS problem is NP-hard. An empirical experiment to investigate the performance of four heuristics in literature versus modifications by switching the shortest with the longest processing time job before scheduling was performed using a set of seven jobs. The seven jobs were Jackknifed to create sets of six jobs each to validate heuristic performances. Eight sets of four jobs randomly chosen from the seven were scheduled to investigate the performance of the heuristics when the number of jobs is equal to or less than the number of second-stage machines. Heuristic performance was measured using makespan and percentage deviation of the makespan from a selected lower bound. Results recommend an ensemble of three heuristics, the best makespan heuristic for jobs less than or equal to four and the two that begin by ordering jobs in increasing processing times, switch the shortest with the longest processing time job then list schedule jobs to machines.

Keywords

• Hybrid-Flow-Shop Scheduling Problem
• Optimisation of Makespan
• Scheduling Heuristic
• Ensemble