Scheduling n jobs on one machine to minimize the maximum lateness with a minimum number of tardy jobs

Scheduling n jobs on one machine to minimize the maximum lateness with a minimum number of tardy jobs

0.00 Avg rating0 Votes
Article ID: iaor20021158
Country: Netherlands
Volume: 40
Issue: 4
Start Page Number: 349
End Page Number: 360
Publication Date: Sep 2001
Journal: Computers & Industrial Engineering
Authors: ,
Abstract:

This study considers the problem of scheduling n jobs, each job having an arrival time, a processing time and a due date, on a single machine with the dual objective of minimizing the maximum lateness subject to obtaining a minimum number of tardy jobs. A simple procedure is introduced to identify two critical jobs from which the maximum lateness is generated for a given sequence. The sequence of jobs between two critical jobs inclusive is called the critical path. On the basis of the critical path, Carlier's binary branching rule is adopted to minimize the maximum lateness. By fixing the position of these two critical jobs for maintaining the minimum maximum lateness, the sequence can further be reordered to reduce the number of tardy jobs. A branch and bound algorithm is presented for this purpose. The algorithm can solve problems with 50 jobs optimally within 5 seconds on a PC Pentium-100.

Reviews

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