Improved Lagrangian relaxation based optimization procedure for scheduling with storage

Publication Type:
Conference Proceeding
IFAC-PapersOnLine, 2019, 52 (13), pp. 100 - 105
Issue Date:
Filename Description Size
1-s2.0-S2405896319311097-main.pdfPublished version592.16 kB
Adobe PDF
Full metadata record
© 2019, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved. 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.
Please use this identifier to cite or link to this item: