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

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

0.00 Avg rating0 Votes
Article ID: iaor1997549
Country: Netherlands
Volume: 44
Issue: 1/2
Start Page Number: 35
End Page Number: 43
Publication Date: Jun 1996
Journal: International Journal of Production Economics
Authors: ,
Keywords: programming: branch and bound
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.