Two Agent Scheduling Problems To Minimize The Maximum Completion Time On Two Uniform Machines

This paper mainly considers the scheduling problem of two agents with preemptive or non-preemptive processing for two machines,in which the processing speed of two machines is constant but may not equal.When the maximum completion time of one agent satisfies a parameter,the maximum completion time of the other is minimum.For the problem of preemptive processing,we consider to improve the algorithm of single agent problem,design the polynomial time optimal algorithm for two agent problem and give it the proof.In addition,we show the algorithm process through two examples.For the non-preemptive processing,we consider the quasi polynomial algorithm of dynamic programming which is from enumeration.And we finally design,prove and illustrate that the algorithm is a fully-polynomial time approximation scheme(FPTAS).