Near-Optimal Solutions for Mold Constraints on Two Parallel Machines

被引：9

作者：

Ben Hmida, Abir ^{[1
,4
]}

Jemmali, Mahdi ^{[2
,3
,4
]}

机构：

[1] Jeddah Univ, Dept Informat Syst, Fac Comp & Informat Technol Khulais, Jeddah, Saudi Arabia

[2] Majmaah Univ, Coll Sci Zulfi, Dept Comp Sci & Informat, Majmaah 11952, Saudi Arabia

[3] Univ Sousse, Mars Lab, Sousse, Tunisia

[4] Monastir Univ, Dept Comp Sci, Higher Inst Comp Sci & Math Monastir, Monastir 5000, Tunisia

来源：

STUDIES IN INFORMATICS AND CONTROL | 2022年 / 31卷 / 01期

关键词：

Mold constraint; Heuristics; Makespan; Scheduling; Local-search; SCHEDULING PROBLEM; MAKESPAN;

D O I：

10.24846/v31i1y202207

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：71 / 78

页数：8

共 50 条

[31] Optimal and near-optimal solutions for 3D structure comparisons
Caprara, A
Lancia, G
FIRST INTERNATIONAL SYMPOSIUM ON 3D DATA PROCESSING VISUALIZATION AND TRANSMISSION, 2002, : 737 - 744
[32] Generalized parallel interference cancellation with near-optimal detection performance
Luo, Zhendong
Zhao, Ming
Liu, Siyang
Liu, Yuanan
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2008, 56 (01) : 304 - 312
[33] Design of Near-Optimal Coding Schemes for Adaptive Modulation with Practical Constraints
Sankar, Hari
Narayanan, Krishna R.
2006 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, VOLS 1-12, 2006, : 5034 - 5039
[34] Near-Optimal and Practical Algorithms for Graph Scan Statistics with Connectivity Constraints
Cadena, Jose
Chen, Feng
Vullikanti, Anil
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA, 2019, 13 (02)
[35] Robust Near-Optimal Coordination in Uncertain Multiagent Networks With Motion Constraints
Guo, Yaohua
Chen, Gang
IEEE TRANSACTIONS ON CYBERNETICS, 2023, 53 (05) : 2841 - 2851
[36] Near-optimal blacklisting
Dimitrakakis, Christos
Mitrokotsa, Aikaterini
COMPUTERS & SECURITY, 2017, 64 : 110 - 121
[37] Visiting near-optimal solutions using local search algorithms
Jacobson, Sheldon H.
Hall, Shane N.
McLay, Laura A.
COMPSTAT 2006: PROCEEDINGS IN COMPUTATIONAL STATISTICS, 2006, : 471 - +
[38] Near-optimal solutions for day-ahead unit commitment
Yang, Dominic
Knueven, Bernard
Watson, Jean -Paul
Ostrowski, James
ELECTRIC POWER SYSTEMS RESEARCH, 2024, 234
[39] Nonlinear optimal and near-optimal controls of a space robotic system via parallel computation
Qu, ZH
Zalewski, J
SPACE ROBOTICS (SPRO'98), 1999, : 103 - 109
[40] Practical Parallel Algorithms for Near-Optimal Densest Subgraphs on Massive Graphs
Sukprasert, Pattara
Liu, Quanquan C.
Dhulipala, Laxman
Shun, Julian
2024 PROCEEDINGS OF THE SYMPOSIUM ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX, 2024, : 59 - 73

← 1 2 3 4 5 →