Single machine scheduling using dominance relation to minimize earliness subject to ready and due times

This paper considers a single machine scheduling problem with the constraints of prespecified ready and due times and the assumption of sequence-dependent setup times. That is, every job is available for processing on the ready time of each job and cannot be processed before the time. Also, every job must be completed before or just on the due time of each job, and no tardy jobs are allowed. This paper proposes an optimization algorithm using dominance relation for the scheduling problem based on the branch-and-bound method to effectively determine the optimum solution so as to minimize the total earliness. In the proposed algorithm, the model size at each node can be reduced by determining the dominance relation to perform branching operation. Furthermore, the strong lower bound is derived by determining the total minimum overlapping time for all unassigned jobs. Although the computational time through the proposed algorithm increases exponentially to solve problems by increasing the number of jobs, the branching operation and strong lower bound using the dominance relation will enhance the computational efficiency. The effectiveness of proposed algorithm will also be reported by simulation results.