Scheduling job families about an unrestricted common due date on a single machine

Scheduling job families about an unrestricted common due date on a single machine

0.00 Avg rating0 Votes
Article ID: iaor1998748
Country: United Kingdom
Volume: 35
Issue: 5
Start Page Number: 1321
End Page Number: 1330
Publication Date: May 1997
Journal: International Journal of Production Research
Authors: ,
Abstract:

We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due date to minimize total weighted earliness and tardiness cost. Jobs are grouped into families where jobs in the same family share a setup: a setup time is required between the processing of two jobs from different families. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. These rates are assessed on a per-period basis when the completion time deviates from its due date. In this paper, we generalize properties from the literature that characterize the structure of an optimal schedule, present a lower bound, propose a branch and bound algorithm and a beam search procedure, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for smaller problem instances. For large problems, we find high quality solutions within a few minutes of CPU time.

Reviews

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