The Constrained Assignment Problem

In this thesis,we consider the constrained assignment problem.It is defined as fol-lows:given m tasks and n workers,the completion time is cij if the task i(1?i?m)is finished by the worker j(1?j?n),each task is assigned to at least two workers togeth-er and each worker is assigned to do no more than one task.We consider such problems are following two objectives:(1)It is to maximize the number of tasks finished;(2)It is to minimize the total completion time when k tasks are finished,where k is a positive integer.We obtain the two results as follows:(1)We design a 2/3-approximation algorithm with time complexity O((m+n)3)to solve the first problem.(2)We present a heuristic algorithm with time complexity O(m3(m+n)2log(m + n))to solve the second problem.At the end,we give some instances and program implementations.