The Generalized Assignment Problem With Genetic Algorithm

Son Teslim Tarihi: 13 Ocak 2022 23:00
Algoritma Yazılım Kodlama Endüstri Mühendisliği Genetic Assignment Problem
The generalized assignment problem (GAP) is a well-known combinatorial optimization problem which involves finding the minimum cost assignment of n jobs to m agents such that each job is assigned to exactly one agent. However, allocating a job to an agent incurs cost and resource consumption and every agent has a resource capacity. The mathematical model of GAP can be formulated as follows:
Minimize∑𝑚 ∑𝑛 𝑐 𝑥 𝑖=1 𝑗=1 𝑖𝑗 𝑖𝑗
s.t. ∑𝑚 𝑥 =1 𝑗=1,⋯,𝑛 𝑖=1 𝑖𝑗
∑𝑛 𝑝𝑥≤𝑏 𝑖=1,⋯,𝑚 𝑗=1 𝑖𝑗 𝑖𝑗 𝑖
𝑥𝑖𝑗 ∈ {0,1} 𝑖 = 1,⋯,𝑚,𝑗 = 1,⋯,𝑛
where cij is the cost of assigning job j to agent i, pij is the resource consumption of assigning job j to agent i, and bi is the resource capacity (availability) of agent i. The binary decision variable xij takes the value 1 if job j is assigned to agent i and 0 otherwise. The first constraint set ensures that each job is assigned to exactly one agent. The second constraint set guarantees that the total resource requirement of the jobs assigned to an agent does not exceed the resource capacity of the agent.
In this project, you are asked to develop a simulated annealing algorithm or a genetic algorithm which solves the Generalized Assignment Problem (GAP). All algorithmic details are left to your creativity! Three problem instances are given for coding, debugging, and reporting purposes. The first problem instance contains 5 agents and 25 jobs. The second problem instance includes 8 agents and 40 jobs. Finally, the third problem instance contains 10 agents and 50 jobs.
You are going to report the solutions found by your algorithm for each given problem instance and all your algorithmic details. You should also compare the quality of the solution you obtain to a lower bound on its optimal value.
review the literature for the chosen algorithm. Then you should continue with the design/development of your algorithm. After finishing the code, you have to analyze and interpret the results provided by your algorithm and draw conclusions.
Eklenen dosyaları görmek için giriş yapınız !

Bu Görev Yayında Değil