A Two-Machine Learning Date Flow-Shop Scheduling Problem with Heuristics and Population-Based GA to Minimize the Makespan

Jian-You Xu, Win-Chin Lin, Yu-Wei Chang, Yu-Hsiang Chung, Juin-Han Chen and Chin-Chia Wu ()
Additional contact information
Jian-You Xu: College of Information Science and Engineering, Northeastern University, Shenyang 110819, China
Win-Chin Lin: Department of Statistics, Feng Chia University, Taichung 40724, Taiwan
Yu-Wei Chang: Department of Statistics, Feng Chia University, Taichung 40724, Taiwan
Yu-Hsiang Chung: Department of Industrial Engineering Automation Operation Intelligence, Micron Memory Taiwan Co., Ltd., Taichung 42152, Taiwan
Juin-Han Chen: Department of Industrial Engineering and Management, Cheng Shiu University, Kaohsiung City 83347, Taiwan
Chin-Chia Wu: Department of Statistics, Feng Chia University, Taichung 40724, Taiwan

Mathematics, 2023, vol. 11, issue 19, 1-21

Abstract: This paper delves into the scheduling of the two-machine flow-shop problem with step-learning, a scenario in which job processing times decrease if they commence after their learning dates. The objective is to optimize resource allocation and task sequencing to ensure efficient time utilization and timely completion of all jobs, also known as the makespan. The identified problem is established as NP-hard due to its reduction to a single machine for a common learning date. To address this complexity, this paper introduces an initial integer programming model, followed by the development of a branch-and-bound algorithm augmented with two lemmas and a lower bound to attain an exact optimal solution. Additionally, this paper proposes four straightforward heuristics inspired by the Johnson rule, along with their enhanced counterparts. Furthermore, a population-based genetic algorithm is formulated to offer approximate solutions. The performance of all proposed methods is rigorously evaluated through numerical experimental studies.

Keywords: scheduling; learning dates; flow-shop; population-based genetic algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/19/4060/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/19/4060/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:19:p:4060-:d:1247161

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().