A three-dimensional matching model for perishable production scheduling

A three-dimensional matching model for perishable production scheduling

0.00 Avg rating0 Votes
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: , ,
Keywords: optimization
Abstract:

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 P under assumption (ii). Polynomial-time algorithms are also proposed to solve other optimization versions of the problem (in two cases, based on the identification of a matroid structure).

Reviews

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