Production-scheduling in Fresh Vegetable Processing

W. Heemskerk BV is one of the largest fresh processed vegetable production companies in Europe. Weekly, more than two million products find their way to well-known supermarket chains and fast-food restaurants in the Netherlands and abroad. The production process consists of two well-defined stages. In the first stage, vegetables are cut and washed into a large range of intermediate products. In the second stage, these products are packaged into various types of packaging material. Most of this work is performed on highly specialized production lines. The processed vegetables have a very short lifetime. This means that the production follows a daily cycle. Each day the entire range of products is produced at least once. In the current situation the production schedule is fixed. Each product is initially assigned to the same machine in the same sequence. To arrive at a feasible production schedule that satisfies all constraints, experienced team leaders manually adjust the schedule during the production day. This practice of manually adjusting the production schedule is not ideal. Due to the complexity of the process, changes in the schedule can only be made very close to the actual production time. At that point many potentially better options have already been excluded. Furthermore, the production process is constantly becoming more complex. New production lines and product recipes are constantly being added. Because of this, the process is a good candidate for combinatorial optimization. In this thesis a mathematical formulation is given for the scheduling problem. The production process includes various process-specific constraints. For example, the production sequence of the different products is restricted because of cross-contamination risks. All these process-specific constraints are included in the model. This results in a continuous-time immediate precedence batch-scheduling model that minimizes the amount of bad changeovers, the idle time in the schedule and the tardiness of the different batches. A first attempt was made to solve the MIP-model by making use of the commercial solver CPLEX. Due to the sheer size of problem instance, this solver is unable to find a feasible solution for the model in a reasonable amount of time. Therefore, a sequential approach is proposed to solve the problem. The sequential approach consists of a number of steps. In the first step, only the packaging orders are scheduled. The solution of this first step is used as input for the second step in which all pre-processing orders are scheduled. A last step is then required to re-solve the schedule of the packaging orders to arrive at an overall feasible production schedule. For each step of this approach, the same commercial solver is utilized. However, due to the sequential approach, the number of variables and constraints in each of the problem instances is greatly reduced. This results in a greatly reduced solution time. The sequential approach is compared to the MIP-based approach using a relatively small problem instance. The results of this comparison show that the sequential approach gives solutions of equal or better quality than the MIP-based approach while requiring considerably less solution time. The capabilities of the sequential approach are further amplified by solving an actual real-world problem instance and by comparing it to the current situation at the case-company.