no. 2
An optimal solution for the budgets assignment problem
RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 873-897

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.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2021043
Classification : 90C90, 90C59, 90C27
Keywords: Regional development, load balancing resources, equity distribution, heuristic, budgeting 
@article{RO_2021__55_2_873_0,
     author = {Jemmali, Mahdi},
     title = {An optimal solution for the budgets assignment problem},
     journal = {RAIRO. Operations Research},
     pages = {873--897},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {2},
     doi = {10.1051/ro/2021043},
     mrnumber = {4253779},
     zbl = {1472.90111},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021043/}
}
TY  - JOUR
AU  - Jemmali, Mahdi
TI  - An optimal solution for the budgets assignment problem
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 873
EP  - 897
VL  - 55
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021043/
DO  - 10.1051/ro/2021043
LA  - en
ID  - RO_2021__55_2_873_0
ER  - 
%0 Journal Article
%A Jemmali, Mahdi
%T An optimal solution for the budgets assignment problem
%J RAIRO. Operations Research
%D 2021
%P 873-897
%V 55
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021043/
%R 10.1051/ro/2021043
%G en
%F RO_2021__55_2_873_0
Jemmali, Mahdi. An optimal solution for the budgets assignment problem. RAIRO. Operations Research, Tome 55 (2021) no. 2, pp. 873-897. doi: 10.1051/ro/2021043

[1] M. Alharbi and M. Jemmali, Algorithms for investment project distribution on regions. Comput. Intell. Neurosci. 2020 (2020) 3607547. | DOI

[2] H. Alquhayz, M. Jemmali and M. M. Otoom, Dispatching-rule variants algorithms for used spaces of storage supports. Discrete Dyn. Nat. Soc. 2020 (2020). | MR | Zbl | DOI

[3] A. C. Alvim and C. C. Ribeiro, A hybrid bin–packing heuristic to multiprocessor scheduling. In: International Workshop on Experimental and Efficient Algorithms. Springer (2004) 1–13.

[4] K. J. Arrow, Economic Welfare and the Allocation of Resources for Invention. Macmillan Education UK, London (1972) 219–236.

[5] B. S. Baker, A new proof for the first-fit decreasing bin-packing algorithm. J. Algorithms 6 (1985) 49–70. | MR | Zbl | DOI

[6] M. Dell’Amico and S. Martello, Optimal scheduling of tasks on identical parallel processors. ORSA J. Comput. 7 (1995) 191–200. | Zbl | DOI

[7] M. Haouari and A. Gharbi, Fast lifting procedures for the bin packing problem. Discrete Optim. 2 (2005) 201–218. | MR | Zbl | DOI

[8] M. Haouari and M. Jemmali, Tight bounds for the identical parallel machine-scheduling problem: Part II. Int. Trans. Oper. Res. 15 (2008) 19–34. | MR | Zbl | DOI

[9] M. Haouari and M. Jemmali, Maximizing the minimum completion time on parallel machines. 4OR 6 (2008) 375–392. | MR | Zbl | DOI

[10] M. Haouari, A. Gharbi and M. Jemmali, Tight bounds for the identical parallel machine scheduling problem. Int. Trans. Oper. Res. 13 (2006) 529–548. | MR | Zbl | DOI

[11] M. Jemmali, Approximate solutions for the projects revenues assignment problem. Commun. Math. App. 10 (2019) 653–658.

[12] M. Jemmali, Budgets balancing algorithms for the projects assignment. Int. J. Adv. Comput. Sci. App. 10 (2019) 574–578.

[13] M. Jemmali, L. K. B. Melhim, S. O. B. Alharbi and A. S. Bajahzar, Lower bounds for gas turbines aircraft engines. Commun. Math. App. 10 (2019) 637–642.

[14] M. Jemmali, L. K. B. Melhim and M. Alharbi, Randomized-variants lower bounds for gas turbines aircraft engines. In: World Congress on Global Optimization. Springer (2019) 949–956.

[15] N. Katoh and T. Ibaraki, Resource Allocation Problems. Springer US, Boston, MA (1999) 905–1006.

[16] H. Kellerer, U. Pferschy and D. Pisinger, Multidimensional knapsack problems. In: knapsack problems. Springer (2004) 235–283. | DOI

[17] E. L. Lawler, J. K. Lenstra, A. H. R. Kan and D. B. Shmoys, Sequencing and scheduling: algorithms and complexityIn: Vol. 4 of Handbooks in Operations Research and Management Science (1993) 445–522. | DOI

[18] S. Martello, D. Pisinger and P. Toth, Dynamic programming and strong bounds for the 0–1 knapsack problem. Manage. Sci. 45 (1999) 414–424. | Zbl | DOI

[19] R. Walter, M. Wirth and A. Lawrinenko, Improved approaches to the exact solution of the machine covering problem. J. Scheduling 20 (2017) 147–164. | MR | Zbl | DOI

[20] D. Pisinger, Dynamic programming on the word ram. Algorithmica 35 (2003) 128–145. | MR | Zbl | DOI

[21] B. Xia and Z. Tan, Tighter bounds of the first fit algorithm for the bin-packing problem. Discrete Appl. Math. 158 (2010) 1668–1675. | MR | Zbl | DOI

Cité par Sources :