Branch And Bound Job Assignment Problem Operations

  • [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

  • The department chair intends to assign classes to 3 professors to teach. There are 6 classes in total, so each professor gets assigned 2 classes each. Each professor ranks the classes that they want in order of preference (1-6, with 6 being most desired). This preference also assigns a score to each class. The department chair then chooses to assign the courses to the professors. If he assigns class xn to professor A then the chair gets the number that the professor scored that class as. He does this until each professor has two classes each. The chair wants to maximize his score. What method should the chair use to assign the classes?

    example: Courses: x1 x2 x3 x4 x5 x6

    Professor A ranking: 1,3,4,5,6,2

    Professor B ranking: 2,3,5,1,6,4

    Professor C ranking: 5,6,4,3,2,1

    So if chair assigns class x1->A, x2->A,x3->b, x4->b, x5->c, x6->c then he would get a score of 1+3+5+1+2+1=12. Obviously this is not optimal but this is a feasible solution.

    Using branch-and-bound method can obtain an optimal solution. I've read how to set up branch-and-bound linear equations but I'm a bit unsure how to do it in this particular case. Can someone perhaps give me a lead that could help me set it up?


    0 Replies to “Branch And Bound Job Assignment Problem Operations”

    Lascia un Commento

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