Abstract
We consider m machines in parallel with each machine capable of producing one specific product type. There are n orders with each one requesting specific quantities of the various different product types. Order j has a release date rj and a due date dj. The different product types for order j can be produced at the same time. We consider various due date related objectives such as the minimization of the maximum lateness Lmax and the total number of late orders ∑Uj. We present polynomial time algorithms for the easy cases and heuristics for NP-hard cases. For minimizing ∑Uj, we also propose an exact algorithm based on Constraint Propagation and bounding strategy. The effectiveness of the algorithms is demonstrated through an empirical study.
Original language | English (US) |
---|---|
Pages (from-to) | 370-389 |
Number of pages | 20 |
Journal | European Journal of Operational Research |
Volume | 168 |
Issue number | 2 SPEC. ISS. |
DOIs | |
State | Published - Jan 16 2006 |
All Science Journal Classification (ASJC) codes
- General Computer Science
- Modeling and Simulation
- Management Science and Operations Research
- Information Systems and Management
Keywords
- Exact algorithm
- Heuristics
- NP-hard
- Order scheduling
- Total number of late orders