An optimal solution for the budgets assignment problem

¹ 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, University of Monastir, Monastir 5000, Tunisia

^* Corresponding author: m.jemmali@mu.edu.sa, mah_jem_2004@yahoo.fr

Received: 8 March 2019
Accepted: 18 March 2021

Abstract

Municipalities are service organizations that have a major role in strategic planning and community development that consider the future changes and society developments, by implementing set of projects with pre-allocated budgets. Projects have standards, budgets and constraints that differ from one community to another and from one city to another. Fair distributing of different projects to municipalities, while ensuring the provision of various capabilities to reach developmental role is NP-Hard problem. Assuming that all municipalities have the same strategic characteristics. The problem is as follows: given a set of projects with different budgets, how to distribute all projects to all municipalities with a minimum budget gap between municipalities. To derive equity distribution between municipalities, this paper developed lower bounds and eleven heuristics to be utilized in the branch-and-bound algorithms. The performance of the developed heuristics, lower bounds and the exact solutions are presented in the experimental study.