Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem

The expansion of the global economy and globalization has increased the need for effective models for production scheduling in multi-factory environment systems. Among the distributed scheduling problems, the distributed flexible job shop scheduling problem (DFJSP) has particularly attracted significant research attention. It represents a typical multi-factory environment where each factory is treated as an individual flexible shop, and each job is allocated to exactly one factory. Compared to the traditional flexible job shop problem (FJSP) system, the solution of distributed flexible job shop scheduling problem setup is particularly difficult and complicated in the sense that it involves solutions of three distinct sub-problems: determining the most suitable factory for each job, selection of machines for all the operations for each factory and determining the sequence of operations for all the machines in each factory.

Mathematical models are crucial tools for studying and solving scheduling problems. Formulating feasible mathematical models do not only helps optimize the system but also help mine relevant information which can be used in scheduling the problem effectively or as future reference. In an effort to solve the distributed flexible job shop scheduling problem, researchers at Huazhong University of Science and Technology: Dr.Leilei Meng, Dr. Chaoyong Zhang, and Mr. Chang Lv (PhD candidate), in collaboration with Dr. Biao Zhang from Liaocheng University and Dr. Yaping Ren from Jinan University, developed four mixed-integer linear programming models and a constraint programming model. Their research work is currently published in the journal, Computers and Industrial Engineering.

In their approach, the four mixed-integer linear programming modes were based on four different modeling ideas: sequence-based, position-based, time-indexed, and adjacent sequence-based. Since these models are not effective for solve large-sized problems, the constraint programming model was formulated based on a combination of interval decision variables and domain filtering algorithms as an alternative approach. Furthermore, the feasibilities of the proposed models were validated through numerical simulations as well as compared to the state-of-the-art algorithms.

Results showed that the mixed-integer linear programming models were only suitable for solving small-scale problems to optimality. In contrast, the constraint programming model was ideal for solving both small- and large-scale problems to optimality. Among the four mixed-integer linear programming models, the sequence-based model was the most effective and produced reliable results. All the models could improve 11 known benchmark solutions instances alongside proving optimality for up to 62 known solutions. Moreover, only the constraint programming model outperformed all the state-of-the-art algorithms in terms of quality and efficiency, making it the best model. Due to its simplicity and ease of application using the presently available solver IBM constraint programming optimizer, the authors noted that it would be highly suitable for practical applications. The following figure shows the Gantt chart of la09 with 2 factories, and its makespan is equal to 436.

In summary, the study is the first ever to formulate mixed-integer linear programming models and implement a constraint programming model for solving the distributed flexible job shop scheduling problem. Based on the results, the constraint programming model was identified as the best approach for efficiently solving both small- and large-scale distributed flexible job shop scheduling problem with desirable quality, and thus a promising solution for practical applications. Moreover, the study results provide useful insights that would enable researchers to find solutions for other distributed scheduling problems by modifying the presented models or formulating new models.