Improved Lagrangian relaxation based optimization procedure for scheduling with storage

摘要

The paper considers the two-stage hybrid flow shop scheduling problem, where the second-stage machines process jobs in predefined batches and the processing of each batch requires a batch-dependent portion of limited storage space. This portion of the storage is seized by a batch from the start of the processing of the jobs, constituting the batch, on the first stage, till the batch has been completed on the second stage. The objective is the total weighted tardiness of the batches with respect to the given due dates. This scheduling problem arises in manufacturing, supply chains of mineral resources and computer systems. One of the approaches to this NP-hard in the strong sense problem is Lagrangian relaxation. The paper presents modifications that allow to significantly improve the performance in comparison with a straightforward Lagrangian relaxation. The effectiveness of the proposed modifications is justified by the results of computational experiments.