Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs

Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs

0.00 Avg rating0 Votes
Article ID: iaor19951330
Country: United Kingdom
Volume: 22
Issue: 2
Start Page Number: 205
End Page Number: 219
Publication Date: Feb 1995
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

The authors consider a single-machine scheduling problem in which every job has a given target start time and a due-date. A job is early if processing commences before its start time and is tardy if it is completed after its due-date. The objective is to minimize the weighted number of early and tardy jobs, with the restriction that the start times and due-dates are ‘agreeable’, i.e., the start times must increase in the same sequence as the due-dates. The authors show that the problem is NP-complete in the strong sense. The complexity issues and algorithms for some special cases of this problem are discussed, and heuristic algorithms are developed for the general problem. Computational experiments are conducted to show the effectiveness of the heuristics.

Reviews

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