Optimal scheduling for letter sorter machines

In this paper three approaches are proposed to generate schedules for the letter sorting machines at CTT–Correios de Portugal SA. The first approach is based on a single machine scheduling model with no setup times. A constructing algorithm and some heuristic procedures were developed to solve the model. The second model includes setup times, making the total time dependent on the job processing sequence. It is based on a typical vehicle routing problem with time windows and solved using a commercial package. The third approach tackles the set of sorting machines as a whole, generating simultaneously the schedules for all machines. It is based on an assignment problem for which commercial software is also available. Computational results are presented for real data gathered at the Lisbon CTC.