Minimizing the weighted number of tardy jobs on a single machine with release dates

Minimizing the weighted number of tardy jobs on a single machine with release dates

0.00 Avg rating0 Votes
Article ID: iaor20084374
Country: Netherlands
Volume: 176
Issue: 2
Start Page Number: 727
End Page Number: 744
Publication Date: Jan 2007
Journal: European Journal of Operational Research
Authors: ,
Keywords: combinatorial analysis, programming: branch and bound
Abstract:

In this paper, we describe an exact algorithm to minimize the weighted number of tardy jobs on a single machine with release dates. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate the proposed exact algorithm solves either weighted or unweighted problems. It solves the hardest problems to date. Indeed, it solves all previously unsolved instances. Its run time is the shortest to date. Scope and purpose: In many industrial sectors, satisfying due dates is a critical issue. Thus, lateness related measures such as the weighted number of tardy jobs are relevant performance measures of schedules in these industries. Our paper studies minimizing the weighted number of tardy jobs on a single machine with release and due dates, and proposes a new exact algorithm. For both weighted and unweighted problems, the exact algorithm solves the largest problems to date.

Reviews

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