View article

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 may have a release date r _j and a due date d _j . The different product types for order j can be produced at the same time. We consider the class of objectives ∑ f _j (C _j ) that includes objectives such as the total weighted completion time ∑ w _j C _j and the total weighted tardiness ∑ w _j T _j of the n orders. We present structural properties of the various problems and a complexity result. In particular, we show that minimizing ∑ C _j when m ≥ 3 is strongly NP-hard. We introduce two new heuristics for the ∑ C _j …