Algorithm Design And Analysis Of Orders On-Line Scheduling Problem

In this thesis we mainly discuss the semi-online scheduling problem for jobs with release time and processing time on m identical parallel machines and analyze the worst performance ratio of the LS algorithm. The objective function is to minimize the maximum completion time of all machines. If the job list has non-decreasing release time and non-increasing processing time, we prove that the worst performance ratio of LS algorithm is not bigger than3/2-1/2m for m∈N+; and7/6is equaled to the worst performance ratio of LS algorithm for m=2. The following content is the arrangement of this thesisIn chapter1we give a brief introduction of Combinational optimization, Approximation algorithm, Scheduling problem and LS algorithm, at the end of this chapter we roughly introduce the model we studied.In chapter2we prove that the worst performance ratio of LS algorithm is not bigger than3/2-1/2m for m∈N+, if the job list has non-decreasing release time and non-increasing processing time. In chapter3we prove that the worst performance ratio of LS algorithm is equaled to7/6for m=2, if the job list has non-decreasing release time and non-increasing processing time...