Efficient Filtering for the Unary Resource with Family-based Transition Times
(2016) International Conference on Principles and Practice of Constraint Programming — Location: Toulouse (5.September.2016)
Files
llncs.pdf
Restricted Access - Adobe PDF
- 751.73 KB
Details
- Authors
- Abstract
- We recently proposed an extension to Vilim's propagators for the unary resource constraint in order to deal with sequence-dependent transition times. While it has been shown to be scalable, it suffers from an important limitation: when the transition matrix is sparse, the additional filtering, as compared to the original from Vilim's algorithm, drops quickly. Sparse transition time matrices occur especially when activities are grouped into families with zero transition times within a family. The present work overcomes this weakness by relying on the transition times between families of activities. The approach is experimentally evaluated on instances of the Job-Shop Problem with Sequence Dependent Transition Times. Our experimental results demonstrate that the approach outperforms existing ones in most cases. Furthermore, the proposed technique scales well to large problem instances with many families and activities.
- Affiliations
Citations
Van Cauwelaert, S., Dejemeppe, C., Monette, J.-N., & Schaus, P. (2016). Efficient Filtering for the Unary Resource with Family-based Transition Times. International Conference on Principles and Practice of Constraint Programming, Toulouse. https://hdl.handle.net/2078.5/229576