This research aims to solve the scheduling problem for a set of batch production lines for packaged sandwiches, based on market demand. The plant has four non-identical production lines, processing an average of 75 product varieties daily. The product variety corresponds to different filling configurations and bread types. Changing from one product type to another on the production line requires cleaning to prevent ingredient residue and changes in packaging materials (film). Additionally, there are administrative constraints related to work shifts, including a lunch break and initial delays for some products due to the time needed to prepare their fillings. This case corresponds to the scheduling problem of processing n jobs on m unrelated parallel machines (UPMSP) with sequence-dependent setup times and availability windows. The use of a GRASP (Randomly Greedy Adaptive Search Procedure) metaheuristic is proposed to minimize the production time for daily orders, thereby improving line efficiency and service level. GRASP includes a construction phase to find a list of feasible candidates and a local search phase to refine the solution. Processing and setup times were obtained through time studies. A setup time matrix was used, considering the product sequence in the scheduling, and a penalty table was used to account for availability constraints, favoring the selection of some products over others. The problem was successfully solved, achieving a 56,3% reduction in daily order completion times, as well as an approximate 90% reduction in the production supervisor's scheduling task.

Keywords

GRASP, Production scheduling, Parallel machine, Setup time, Makespan.