Recent advances in MILP and CP Modeling for Distributed Hybrid Flow Shop Scheduling Problems with Sequence-Dependent Setup Times

In the modern landscape of manufacturing, the shift towards globalization and decentralization has reshaped production processes. Today, it is no longer isolated single-factory operation environment; instead, it is multi-factory production systems. Multi-factory production systems refer to a setup where a company or organization operates multiple manufacturing facilities or factories, often located in different geographical locations. These facilities may produce the same or different products, and they are interconnected to streamline production and optimize resource utilization. Distributed scheduling scenarios involve the allocation of tasks, resources, and time slots across multiple nodes or entities in a decentralized manner. This concept is often applied in manufacturing, logistics, and other industries where efficient scheduling and resource allocation are critical. These distributed scheduling scenarios bring forth new challenges, including factory selection, location optimization, and intricate decision-making processes. However, they also offer opportunities to enhance production efficiency and reduce costs. Consequently, both manufacturers and researchers have been increasingly drawn to the complexities of distributed scheduling.

In distributed scheduling, one problem that has garnered significant attention is the Distributed Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup Times (DHFSP-SDST). This problem arises in various industries, including electronics, textiles, semiconductors, paper manufacturing, and logistics. DHFSP-SDST involves multiple factories, each operating as a Hybrid Flow Shop Problem (HFSP) environment. To solve DHFSP-SDST, three critical sub-problems must be addressed: factory selection, machine selection, and job sequencing. Furthermore, the introduction of sequence-dependent setup times between adjacent jobs on the same machine adds an additional layer of complexity to this already challenging problem.

In the context of scheduling problems, especially novel ones like DHFSP-SDST, obtaining optimal solutions through exact algorithms holds paramount importance. These optimal solutions serve as a benchmark, revealing the inherent characteristics of the scheduling problem and providing a reference point for the development of approximate methods. Exact algorithms, often based on Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP) models, have become increasingly popular. Notably, the performance of MILP and CP models has significantly improved over the years, thanks in part to advanced solving software such as CPLEX and GUROBI.

In a recent study published in the Journal Swarm and Evolutionary Computation by a team of esteemed researchers from Liaocheng University, Jinan University, and Huazhong University of Science and Technology. In this study, Dr. Leilei Meng, Dr. Kaizhou Gao, Dr. Biao Zhang, Professor Hongyan Sang, Associate Professor Yaping Ren, and Professor Zhang Chaoyong have made important contributions to the field of DHFSP-SDST. Their work includes the formulation of three novel MILP models and an efficient CP model to solve this intricate scheduling problem.

In their study, the authors described the DHFSP-SDST problem that it encompasses a scenario where ‘𝑛’ jobs need to be processed in ‘𝑛𝑓’ factories, each operating as HFSP environment. Importantly, sequence-dependent setup times are considered between two consecutive jobs on the same machine, adding a layer of complexity. Their key assumptions for DHFSP-SDST include:

• Each job can be assigned to exactly one factory.
• All jobs must follow a predefined sequential order through all stages.
• In each stage, each job can only be assigned to a single machine.
• Machines cannot process more than one operation at a time.
• All jobs and machines in all factories are available at time zero.
• The initial adjustments must be completed before starting the first job on any machine.
• Once started, a job cannot be interrupted.
• Processing times for all jobs on all machines are known in advance.

The objective of DHFSP-SDST is to solve three sub-problems: factory selection, machine selection, and job sequencing while minimizing the makespan, i.e., the total time required to complete all jobs.

The authors developed three novel MILP models based on two different modeling ideas: adjacent sequence-based modeling, and sequence-based modeling. To provide a comprehensive comparison, the research team conducted an in-depth analysis of these models, considering factors such as the number of binary decision variables (NB), the number of continuous decision variables (NL), the number of constraints (NC), solution performance (CS), solution time (Time), and the gap between obtained and optimal solutions.

According to the authors, for the Same-DHFSP-SDST (S-DHFSP-SDST) instances, the sequence-based modeling idea emerged as the most efficient, outperforming the other two modeling approaches. Notably, the sequence-based model solved more instances to optimality and exhibited shorter solution times. On the other hand, the machine position-based modeling approach struggled to find optimal solutions for some instances. While in the case of the Distinct-DHFSP-SDST (D-DHFSP-SDST) instances, the sequence-based modeling idea once again proved superior, solving the most instances to optimality. However, all three novel MILP models significantly outperformed the existing models from previous studies. Moreover, the authors introduced an efficient CP model to solve DHFSP-SDST, offering a viable alternative to the traditional MILP models. The CP model exhibited promising results, solving all DHFSP-SDST instances to optimality within a reasonable time frame. Furthermore, the proposed MILP and CP models were extended to solve DHFSP-SDST with considering other constraints, such as no-idle constraint, no-wait constraint, transportation constraint and blocking constrict.

In conclusion, the study by Dr. Leilei Meng and colleagues is an important contribution in solving the Distributed Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup Times (DHFSP-SDST). Their work not only formulates novel MILP models but also introduces an efficient CP model, expanding the toolkit for tackling this complex scheduling problem. The research outcomes have the potential to facilitate manufacturing and production scheduling, offering manufacturers valuable tools to optimize their multi-factory production systems, ultimately enhancing efficiency and reducing costs.