Profitability of a multi-model manufacturing line versus multiple dedicated lines

We study a problem to decide which of the two manufacturing configurations - multiple dedicated lines or a single multi-model manufacturing line - is economically more preferable for manufacturing products of several types in a given time period. The goal of employing any of the two configurations is to maximize the total profit, subject to the product demand and manufacturing time constraints. The selection problem is reduced to two optimization problems, for one of which a polynomial time algorithm is developed, and NP-hardness is demonstrated for the other. A dynamic programming algorithm, a constructive greedy heuristic, a randomized heuristic and a local search algorithm with steepest ascent hill climbing are presented for the NP-hard problem. Computer experiments with the heuristics, local search algorithm and a commercial solver of the corresponding integer linear programming problem are described, which demonstrated appropriate quality of the heuristic and local search solutions. The proposed methodology and software can be used to evaluate different input data scenarios while making a selection decision between the two manufacturing configurations. The product demand and selling prices, setup and manufacturing times, demand and production cancellations are the parameters that affect the selection decision.