A global constraint for total weighted completion time

Kovacs, A.;Beck, J.C.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • Kovacs, A.
    Author
  • Beck, J.C.
    Author
Abstract
We introduce a novel global constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the constraint, an O(n/sup 4/ ) algorithm is proposed, which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed global constraint significantly improves the performance of constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. Since our eventual goal is to use the global constraint as part of a larger optimization problem, we view this performance as very promising. We also sketch the application of the global constraint to cumulative resources and to problems with multiple machines.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Kovacs, A., & Beck, J. C. (2007). A global constraint for total weighted completion time. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 112-126). Springer-verlag. https://hdl.handle.net/2078.5/220774