Article ID: | iaor20001494 |
Country: | Netherlands |
Volume: | 92 |
Issue: | 1 |
Start Page Number: | 1 |
End Page Number: | 15 |
Publication Date: | Mar 1999 |
Journal: | Discrete Applied Mathematics |
Authors: | Arbib Claudio, Pacciarelli Dario, Smriglio Stefano |
Keywords: | optimization |
In the production of perishable goods, particular stress is often given to performance indicators generally less critical in such manufacturing settings as metal-cutting, or mechanical/electronic assembly. For instance, in food or biochemical productions, a prominent interest of the producer is to reduce the time from distribution to the so-called best-before end. A scheduling problem with a goal of this sort is here addressed. The decision variables considered are launching and completion times of parts in a production line with critical aspects in the initial and/or final stages. The basic problem is to find an assignment of a maximum number of products to launching and completion times, so that no two products are assigned the same launching or completion time: feasible solutions have therefore the form of three-dimensional matchings. The problem is studied under two independent respects, assuming either (i) the relative perishability of products or (ii) the feasibility of launching/completion time pairs not affected by the intermediate transformation stage. We show that the problem is NP-Complete, even under such a ranking assumption as (i), whereas is in