Friday , May 20 2022

Near-Optimal Solutions for Mold Constraints on Two Parallel Machines

Abir BEN HMIDA1,4*, Mahdi JEMMALI2,3,4
1 Department of Information Systems, Faculty of Computer and Information Technologies at Khulais,
Jeddah University, Saudi Arabia
2 Department of Computer Science and Information, College of Science at Zulfi, Majmaah University,
Majmaah, 11952, Saudi Arabia
3 Mars Laboratory, University of Sousse, Sousse, Tunisia
4 Department of Computer Science, Higher Institute of Computer Science and Mathematics of Monastir,
Monastir University, Monastir, 5000, Tunisia (*Corresponding author),,

Abstract: This paper investigates the mold constraints for the two parallel machines problem. The goal is to minimize the makespan. The resource constraint can be defined as a mold. This constraint is also defined as jobs with conflict. Two jobs can’t be executed by the two machines simultaneously. The problem is proved to be a non-deterministic polynomial NP-hard one. Different heuristics have been proposed in this paper to solve the studied problem. A novel meta-heuristics algorithm is developed to enhance the proposed heuristics. The computational results and discussions show the performance of the proposed solutions. A different class of instances is implemented to test the proposed heuristics. The results show that the developed heuristics reaches the optimal solution in 96.4% of instances. Therefore, the obtained results represent near-optimal solutions for the studied problem.

Keywords: Mold constraint, Heuristics, Makespan, Scheduling, Local-search.


Abir BEN HMIDA, Mahdi JEMMALI, Near-Optimal Solutions for Mold Constraints on Two Parallel Machines, Studies in Informatics and Control, ISSN 1220-1766, vol. 31(1), pp. 71-78, 2022.