Efficient Algorithms for The Multi-Stage Flexible Flow Shop Scheduling Problem with Transportation and Unloading Times
DOI:
https://doi.org/10.23055/ijietap.2024.31.4.9701Abstract
Improving efficiency in multi-stage flexible flowshop operations is essential for modern industrial systems. Optimizing total completion time while simultaneously considering the unloading and transportation times is vital for enhanced productivity and cost-effectiveness. This study delves into the intricate realm of flexible flow shop scheduling, particularly focusing on scenarios prevalent in modern manufacturing processes such as sand casting. Despite limited exploration in prior literature for particular cases, the significance of this problem underscores the pressing need for efficient algorithms and the exploration of new problem properties. Notably, we unveil the symmetry inherent in the problem, where scheduling from the initial stage to the final one, or vice versa, yields identical optimal solutions, thereby augmenting solution quality. Given the strongly NP-Hard nature of the problem, approximate solutions are preferred, especially for medium to large-scale instances. To address this challenge, we propose a novel two-phase heuristic approach, encompassing both a constructive phase and an improvement phase. Leveraging an existing efficient heuristic tailored for parallel machine scheduling, our method extends to efficiently incorporate considerations for unloading and transportation times. The efficacy of the two-phase heuristic lies in its ability to consistently generate high-quality schedules at each stage. Furthermore, we introduce efficient lower bounds derived from estimating the minimum idle time within each stage, drawing from insights in polynomial parallel machine scheduling with a focus on flow time minimization in preceding stages. These lower bounds serve as critical benchmarks for evaluating the performance of the two-phase heuristic against the relative gap performance measure. Extensive experimentation on benchmark test problems underscores the effectiveness of our proposed algorithms, with results demonstrating an average computation time of 9.48 seconds and a mean relative gap of only 2.42% across varying job and stage quantities up to 200 jobs and 10 stages.
Published
How to Cite
Issue
Section
License
The Author(s) must formally transfer each article's copyright before publication in the INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING. Such transfer enables the Journal to defend itself against plagiarism and other forms of copyright infringement. Your cooperation is appreciated.
You agree that the copyright of your article to be published in the INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING - THEORY, APPLICATIONS, AND PRACTICE is hereby transferred, throughout the World and for the full term and all extensions and renewals thereof, to INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING - THEORY, APPLICATIONS, AND PRACTICE.
The Author(s) reserve(s): (a) the trademark rights and patent rights, if any, and (b) the right to use all or part of the information contained in this article in future, non-commercial works of the Author's own, or, if the article is a "work-for-hire" and made within the scope of the Author's employment, the employer may use all or part of the information contained in this article for intra-company use, provided the usual acknowledgments are given regarding copyright notice and reference to the original publication.
The Author(s) warrant(s) that the article is Author's original work and has not been published before. If excerpts from copyrighted works are included, the Author will obtain written permission from the copyright owners and credit the article's sources.
The author also warrants that the article contains no libelous or unlawful statements and does not infringe on the rights of others. If the article was prepared jointly with other Author(s), the Author agrees to inform the co-Author(s) of the terms of the copyright transfer and to sign on their behalf; or in the case of a "work-for-hire," the employer or an authorized representative of the employer.
The journal does not provide the author copy of the final paper when it is published. The author(s) can make(s) a subscription to INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING - THEORY, APPLICATIONS, AND PRACTICE if they want to get the final paper that has already been published.
The journal is registered with the Library of Congress (ISSN # 1943-670X). All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the journal.
The author reserves patent and trademark rights and the right to use all or part of the information contained in the article in future non-commercial works.
