Two-stage, single-lot, lot streaming problem for a hybrid flow shop

摘要

In this paper, we address a single-lot, lot streaming problem for a two-stage hybrid flow shop, which consists of one machine at Stage 1 and two parallel (identical) machines at Stage 2. The objective is to minimize makespan. The lot is to be split into sublots each of which is processed first on the machine at Stage 1, and then, on one of the machines at Stage 2. A sublot-attached removal time is incurred after processing each sublot at Stage 1. First, we assume the number of sublots for the lot to be known a priori and develop closed-form expressions to obtain optimal, continuous sublot sizes for this case. Then, we consider determination of an optimal number of sublots in addition to their sizes. We develop an upper bound on the number of sublots, , and use an algorithm of complexity in conjunction with the closed-form expressions for sublot sizes to obtain an optimal solution. We also address the problem of determining number of sublots and integer sublot sizes, and propose a heuristic method for its solution that relies on some key results from the continuous case of the problem. The results of our numerical experimentation reveal the efficacy of the proposed method to obtain near-optimal integer sublot sizes and makespan values that are within 2.35 % of the true optimum for the testbed of data used, each obtained within a few seconds of CPU time.