Near-Optimal Solutions for Mold Constraints on Two Parallel Machines

Abir BEN HMIDA^1,4*, Mahdi JEMMALI^2,3,4
1 Department of Information Systems, Faculty of Computer and Information Technologies at Khulais,
Jeddah University, Saudi Arabia
² Department of Computer Science and Information, College of Science at Zulfi, Majmaah University,
Majmaah, 11952, Saudi Arabia
³ Mars Laboratory, University of Sousse, Sousse, Tunisia
⁴ Department of Computer Science, Higher Institute of Computer Science and Mathematics of Monastir,
Monastir University, Monastir, 5000, Tunisia
a.hhmida@uj.edu.sa (*Corresponding author), m.jemmali@mu.edu.sa, mah_jem_2004@yahoo.fr

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.

>>FULL TEXT: PDF

CITE THIS PAPER AS:
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. https://doi.org/10.24846/v31i1y202207