Scheduling of parallel machines with sequence-dependent batches and product incompatibilities in an automotive glass facility

This application is motivated by a complex real-world scheduling problem found in the bottleneck workstation of the production line of an automotive safety glass manufacturing facility. The scheduling problem consists of scheduling jobs (glass parts) on a number of parallel batch processing machines (furnaces), assigning each job to a batch, and sequencing the batches on each machine. The two main objectives are to maximize the utilization of the parallel machines and to minimize the delay in the completion date of each job in relation to a required due date (specific for each job). Aside from the main objectives, the output batches should also produce a balanced workload on the parallel machines, balanced job due dates within each batch, and minimal capacity loss in the batches. The scheduling problem also considers a batch capacity constraint, sequence-dependent processing times, incompatible product families, additional resources, and machine capability. We propose a two-phase heuristic approach that combines exact methods with search heuristics. The first phase comprises a four-stage mixed-integer linear program for building the batches; the second phase is based on a Greedy Randomized Adaptive Search Procedure for sequencing the batches assigned to each machine. We conducted experiments on instances with up to 100 jobs built with real data from the manufacturing facility. The results are encouraging both in terms of computing time—5 min in average—and quality of the solutions—less than 10 % relative gap from the optimal solution in the first phase and less than 5 % in the second phase. Additional experiments were conducted on randomly generated instances of small, medium, and large size.

MILP:

Mixed-integer linear program

GRASP:

Greedy randomized adaptive search procedure

MES:

Manufacturing execution system

SBPSP:

Single batch-processing scheduling problem

\(\mathcal J \) :

Set of jobs

\(\mathcal H \) :

Set of machines

\(\mathcal I \) :

Set of possible batches on any machine

\(\mathcal C \) :

Set of existing additional resource (cast) references

\(\mathcal B \) :

Set of product families

\(\varOmega \) :

Set of constraints (2) through (8)

\(Z_s (s=1, ...,4)\) :

Objective function for stage \(s\) in the batching phase

\(Z_s^*\) :

Best objective function value found in stage \(s\) of the batching phase

\(T(S)\) :

Total tardiness incurred by solution \(S\)

\(\varphi (S)\) :

Utilization level penalty for solution \(S\)

\(f(S)\) :

Penalized objective value for solution \(S\)

\(a_h(S)\) :

Real makespan value for machine \(h\) for solution \(S\)

\(n\) :

Number of jobs (glass parts)

\(h\) :

Number of parallel batch processing machines (furnaces)

\(l_j\) :

Width of the part that corresponds to job \(j\)

\(d_j\) :

Due date for job \(j\)

\(f_j\) :

Product family of job \(j\)

\(w_h\) :

Capacity of the batches assigned to machine \(h\)

\(m_{jh}\) :

1 if job \(j\) can be processed in machine \(h;\) 0 otherwise

\(p_{jh}\) :

Processing time for job \(j\) if processed in machine \(h\)

\(s_c\) :

Quantity of available resources for reference \(c\)

\(r_{jc}\) :

1 if job \(j\) requires a cast of reference \(c;\) 0 otherwise

\(\eta \) :

Maximum deterioration allowed for \(Z_1^*\)

\(\vartheta \) :

Maximum deterioration allowed for \(Z_2^*\)

\(\chi \) :

Maximum deterioration allowed for \(Z_3^*\)

\(ns\) :

Number of iterations of the GRASP algorithm

\(V_h\) :

Makespan target value for machine \(h\) for each problem instance

\(\psi \) :

Pre-defined minimum relative utilization level

\(\lambda \) :

Pre-defined threshold for utilization level before stage 4 of the batching phase

\(x_{jhi}\) :

1 if job \(j\) is assigned to batch \(i\) on machine \(h;\) 0 otherwise

\(y_{hi}\) :

1 if any job is allocated to batch \(i\) on machine \(h;\) 0 otherwise

\(q\) :

Maximum workload that is assigned to any machine

\(g\) :

Maximum slack on any batch

\(s_{hi}\) :

Unused capacity (length) of batch \(i\) on machine \(h\)

This work was partially funded by the Industrial Engineering Department at Universidad de los Andes. We also thank Fair Isaac Corporation for providing us with access to Xpress-MP optimization software under the Academic Partner Program subscribed with Universidad de los Andes.

Authors and Affiliations

1. Departamento de Ingeniería Industrial, Centro para la Optimización y Probabilidad Aplicada (COPA), Universidad de los Andes, Cr 1E No. 19A-10, ML711 , Bogotá, Colombia

   Alvaro J. Lozano & Andrés L. Medaglia

Corresponding author

Correspondence to Andrés L. Medaglia.

Reprints and permissions