A multiple-criterion model for machine scheduling

A multiple-criterion model for machine scheduling

0.00 Avg rating0 Votes
Article ID: iaor2008153
Country: United Kingdom
Volume: 6
Issue: 1
Start Page Number: 7
End Page Number: 16
Publication Date: Jan 2003
Journal: Journal of Scheduling
Authors: ,
Keywords: programming: multiple criteria
Abstract:

We consider a scheduling problem involving a single processor being utilized by two or more customers. Traditionally, such scenarios are modeled by assuming that each customer has the same criterion. In practice, this assumption may not hold. Instead of using a single criterion, we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated based on their individual criteria. We examine three basic scheduling criteria: minimizing makespan, minimizing maximum lateness, and minimizing total weighted completion time. Although determining a minimum-cost schedule according to any one of these criteria is polynomially solvable, we demonstrate that when minimizing a mix of these criteria, the problem becomes NP-hard.

Reviews

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