A three-dimensional matching model for perishable production scheduling Original Research Article

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).