Job Assignment Problem Using Branch And Bound Algorithm

January 21st, 2017, 10:35 AM#1


Job assignment problem solve with Branch and Bound algorithm

I started doing Branch and Bound Algorithm for assignment problem in C++ and i can't find the right solution. First of all assignment problem example:


Ok so each person can be assigned to one job, and the idea is to assign each job to one of the person so that all the jobs are done in the quickest way.

Here is my code so far:

Code:

#include "Matrix.h" // Program to solve Job Assignment problem // using Branch and Bound #include <limits.h> #include <vector> #include <algorithm> using namespace std; template<class T> NUM getCost(Matrix& matrix, size_t x, size_t y, vector<bool>& colUsed); void run(Matrix& matrix, vector<size_t>& assignedJobs); int main() { Matrix matrix; matrix.setMatrix(N); matrix.print(); vector<size_t> assignedJobs; run(matrix, assignedJobs); cout << assignedJobs[0]; /* cout << "size:E " << v.size() << endl; for (vector<NUM>::iterator i = v.begin(); i != v.end(); i++) { cout << *i << endl; } */ return 0; } // remember to use x only LOCALLY!!! NUM getCost(Matrix& matrix, size_t x, size_t y, vector<bool>& colUsed) { // pathCost NUM pathCost = matrix.matrix[x++][y]; for (size_t col = 0; col < matrix.size(); col++) { if (!colUsed.at(col)) { NUM min = #if defined NUM_INT INT_MAX; #endif #if defined NUM_DBL DBL_MAX; #endif size_t row = x; for (; row < matrix.size(); row++) { if (min > matrix.matrix[row][col]) { min = matrix.matrix[row][col]; } } pathCost += min; } } return pathCost; } void run(Matrix& matrix, vector<size_t>& assignedJobs) { // array of used columns vector<bool> colUsed; for (size_t i = 0; i < matrix.size(); i++) { colUsed.push_back(false); } for (size_t row = 0; row < matrix.size(); row++) { size_t col = 0; // bombona while (colUsed.at(col++)); col--; // choose the best job for the current worker vector<NUM> jobs; // get all the job costs from which to choose the smallest // row++ jobs.push_back(getCost(matrix, col, row, colUsed)); // iterator at the position of the smallest element of jobs vector<NUM>::iterator i_min = min_element(jobs.begin(), jobs.end()); // index of the smallest element in jobs size_t index = (size_t)distance(jobs.begin(), i_min); colUsed.at(index) = true; assignedJobs.push_back(index); } }
I know i might be out of track. I didn't use lower bound in the beginning, i'm actually a little confused how this algorithm exactly works. So even step by step walktrough through the algorithm would be helpful.
  • [1]

    V. Balachandran, “An integer generalized transportation model for optimal job assignment in computer networks”, Working Paper 34-72-3, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pa. (November, 1972).Google Scholar

  • [2]

    A. Charnes, W.W. Cooper, D. Klingman and R. Niehaus, “Static and dynamic biased quadratic multi-attribute assignment models: solutions and equivalents”, Center for Cybernetic Studies, Research Report CS 115, The University of Texas, Austin, Texas (January, 1973).Google Scholar

  • [3]

    R.J. Dakin, “A tree search algorithm for mixed integer programming problems”,Computer Journal 8 (3) (1965) 250–255.Google Scholar

  • [4]

    A. DeMaio and C. Roveda, “An all zero–one algorithm for a certain class of transportation problems”,Operations Research 19 (6) (1971) 1406–1418.Google Scholar

  • [5]

    A.M. Geoffrion, “An improved implicit enumeration approach for integer programming”,Operations Research 17 (3) (1969) 437–454.Google Scholar

  • [6]

    A.M. Geoffrion, “Lagrangean relaxation for integer programming”,Mathematical Programming Study 2 (1974) 82–114.Google Scholar

  • [7]

    A.M. Geoffrion and G.W. Graves, “Multicommodity distribution system design by benders decomposition”,Management Science 20 (5) (1974) 822–844.Google Scholar

  • [8]

    H. Greenberg and R.L. Hegerich, “A branch search algorithm for the knapsack problem”,Management Science 16 (5) (1970) 327–332.Google Scholar

  • [9]

    M.D. Grigoriadis, D.T. Tang and L.S. Woo, “Considerations in the optimal synthesis of some communication networks”, Presented at the 45th Joint National Meeting of the Operations Research Society of America and The Institute of Management Sciences, Boston, Mass., April 22–24, 1974.Google Scholar

  • [10]

    D. Gross and C.E. Pinkus, “Optimal allocation of ships to yards for regular overhauls”, Tech. Memorandum 63095, Institute for Management Science and Engineering, The George Washington University, Washington, D.C. (May, 1972).Google Scholar

  • [11]

    G.P. Ingargiola and J.F. Korsh, “Reduction algorithm for zero–one single knapsack problems”,Management Science 20 (4) Part I (1973) 460–463.Google Scholar

  • [12]

    D. Klingman and J. Stutz, “Computational testing on an integer generalized network code”, Presented at the 45th Joint National Meeting of the Operations Research Society of America and The Institute of Management Sciences, Boston, Mass., April 22–24, 1974.Google Scholar

  • [13]

    J.R. Lourie, “Topology and computation of the generalized transportation problem”,Management Science 11 (1) (1964) 177–187.Google Scholar

  • [14]

    V. Srinivasan and G. Thompson, “An algorithm for assigning uses to sources in a speical class of transportation problems”,Operations Research 21 (1) (1973) 284–295.Google Scholar

  • 0 Replies to “Job Assignment Problem Using Branch And Bound Algorithm”

    Lascia un Commento

    L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *