Order scheduling in an environment with dedicated resources in parallel

We consider in 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 Sigma f(j)(C(j)) that includes objectives such as the total weighted completion time Sigma w(j) C(j) and the total weighted tardiness Sigma 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 F Cj when m >= 3 is strongly NP-hard. We introduce two new heuristics for the Sigma C(j) objective. An empirical analysis shows that our heuristics outperform all heuristics that have been proposed for this problem in the literature.