Single-machine two-objective sorting and scheduling

Author: Wan Guohua
Publisher:
Publish Date: 2004-08-01
Features: The second one is a single machine scheduling problem with distinct due windows to minimize total weighted earliness and tardiness. A mathematical formulation is presented and several important properties of the problem are studied. Then an optimal timing algorithm to decide job completion times for a given job sequence is proposed. The Tabu search scheme is employed together with the optimal timing algorithm to generate job sequences and final schedules. Several experiments were designed and carried out to demonstrate the performance of the proposed approach.
The first one is a single machine scheduling problem to minimize the total weighted earliness subject to a minimal number of tardy jobs. First, several properties of the problem are discussed in analyzing the problem. Then, a heuristic algorithm of time complexity O(n^2) and an efficient branch and bound algorithm are proposed. The computational experiments show that the heuristic algorithm is effective in terms of the quality of the solutions in most instances while the branch and bound algorithm is efficient for medium-sized problems.