Order scheduling in an environment with dedicated resources in parallel

Order scheduling in an environment with dedicated resources in parallel

0.00 Avg rating0 Votes
Article ID: iaor2008724
Country: United Kingdom
Volume: 8
Issue: 5
Start Page Number: 355
End Page Number: 386
Publication Date: Oct 2005
Journal: Journal of Scheduling
Authors: , ,
Keywords: heuristics, heuristics: tabu search
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 may have 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 the class of objectives ∑ fj(Cj) that includes objectives such as the total weighted completion time ∑ wj Cj and the total weighted tardiness ∑ wj Tj of the n orders. We present structural properties of the various problems and a complexity result. In particular, we show that minimizing ∑ Cj when m ≥ 3 is strongly NP-hard. We introduce two new heuristics for the ∑ Cj objective. An empirical analysis shows that our heuristics outperform all heuristics that have been proposed for this problem in the literature.

Reviews

Required fields are marked *. Your email address will not be published.