Task Assignment Problem Solved by Continuous Hopfield Network
The task assignment problem with non uniform communication costs (TAP) consists in finding an assignment of the tasks to the processors such that the total execution and communication costs is minimized. This problem is naturally formulated as 0-1 quadratic programming subject to linear constraints (QP). In this paper, we propose a new approach to solve the task assignment problem with non uniform communication costs using the continuous Hopfield network (CHN). This approach is based on some energy or Lyapunov function, which diminishes as the system develops until a local minimum value is obtained. We show that this approach is able to determine a good solution for this problem. Finally, some computational experiments solving the task assignment problem with non-uniform communication costs are shown.
Keywords: Combinatorial optimization, Continuous Hopfield network, Multiprocessor systems, Quadratic 0-1 programming, Task assignment problem
Download Full-Text
ABOUT THE AUTHORS
Ettaouil Mohamed
UFR: Scientific Computing and Computer sciences, Engineering sciences, Modeling and Scientific Computing Laboratory, Faculty of Science and Technology. University Sidi Mohamed Ben Abdellah, Morocco
Loqman Chakir
Department of Computer Engineering, High School of technology, Moulay Ismail University, B. P. 3103, 50000, Toulal, Meknes, Morocco
Hami Youssef
UFR: Scientific Computing and Computer sciences, Engineering sciences, Modeling and Scientific Computing Laboratory, Faculty of Science and Technology. University Sidi Mohamed Ben Abdellah, Morocco
Haddouch Khalid
UFR: Scientific Computing and Computer sciences, Engineering sciences, Modeling and Scientific Computing Laboratory, Faculty of Science and Technology, University Sidi Mohamed Ben Abdellah, Morocco
Ettaouil Mohamed
UFR: Scientific Computing and Computer sciences, Engineering sciences, Modeling and Scientific Computing Laboratory, Faculty of Science and Technology. University Sidi Mohamed Ben Abdellah, Morocco
Loqman Chakir
Department of Computer Engineering, High School of technology, Moulay Ismail University, B. P. 3103, 50000, Toulal, Meknes, Morocco
Hami Youssef
UFR: Scientific Computing and Computer sciences, Engineering sciences, Modeling and Scientific Computing Laboratory, Faculty of Science and Technology. University Sidi Mohamed Ben Abdellah, Morocco
Haddouch Khalid
UFR: Scientific Computing and Computer sciences, Engineering sciences, Modeling and Scientific Computing Laboratory, Faculty of Science and Technology, University Sidi Mohamed Ben Abdellah, Morocco