Optimization Algorithms On Bin Packing Problem With Conflicts

Bin packing problem is a fundamental combinatorial optimization problem,which arouses many scholars’ attention in the early1970s. However, with thedevelopment of computer science and production technology, classical bin packingproblem can not meet people’s requirements in the actual production and reallife. As a result, many new models appear, including bin packing problem withconflicts. Unlike the classical bin packing problem, some pairs of items may be inconflicts and cannot be assigned to the same bin. In this paper, we will discussthe bin packing problem with conflicts, the open-end bin packing problem andthe lazy bureaucrat scheduling game problem.Firstly, we consider three models of the bin packing with conflicts: weightedgraph bin packing problem with conflicts, directed graph bin packing problemwith conflicts, on-line bin packing problem with conflicts. Weighted graph binpacking problem with conflicts means that items with conflicts can be packedinto a bin but with a restriction of tolerance degree. We give a modified packingalgorithm First Fit and prove that the classical packing algorithms have no finiteratio to solve this problem. For directed graph bin packing problem with conflicts,First Fit and Next Fit respectively has a approximation ratio3/2and1.7whenthe conflict graph is restricted to tree. For some subgraphs of perfect graph, wepresent on-line algorithm LFF and its corresponding competitive ratio.Secondly, we study a variant of the open-end bin packing problem, the open-end bin packing with conflicts problem(OBPC), where some pairs of items may bein conflicts and cannot be assigned to the same bin. It is a generalization of boththe open-end bin packing problem and the vertex coloring problem. We first showthat for the general OBPC problem, the classical packing algorithms like First Fit,Next Fit etc. do not work, then we give a modified packing algorithm IF F withthe asymptotic worst-case ratio of3, and the ratio becomes to2when the conflictgraph is restricted to bipartite graph. We also consider the Size Direct-OBPCproblem and show that the asymptotic worst-case ratio of F F D is no more than3/2. Finally, we consider three models of the lazy bureaucrat scheduling prob-lem. We prove that Nash equilibrium solutions exist under certain conditions.We define the corresponding/potential function0, in order to find the Nashequilibrium solutions exist conditions. And we present dynamic programmingbased algorithm for single and multiple machine conditions, which is computed inpseudo-polynomial time. Furthermore, we adopt the concept of/price of anar-chy0to compare the cost of the worst Nash equilibrium with the social optimum,under three kinds of objective: selfish lazy bureaucrat scheduling game, adversarylazy bureaucrat scheduling game and mixed lazy bureaucrat scheduling game. Theprice of anarchy is1+α for adversary lazy bureaucrat scheduling game, however,the price of anarchy is no more than1+α for selfish lazy bureaucrat schedulinggame and selfish lazy bureaucrat scheduling game.