Online Sort Of Parallel To The Workpiece And A Class Of Three-stage Scheduling Problem

In this thesis we consider online scheduling malleable parallel jobs on two identical machines and a supply chain scheduling of three stages. It is split up into four chapters.In chapter1, we first introduce some preliminary concepts related to the scheduling problems and summarize recent results and our results.In chapter2, we study online scheduling of malleable parallel jobs on two identical machines. For the job Ji, the execution time is tj=pj,when it is processed on one machine, and the execution time is tj=Pj/2+Cj,when it is processed on two machines, where cj is the setup time of job Jj. The objective is to minimize the makespan. We first present an online algorithm with competitive ratio of1+α1where α1=(5^1/2-1)/2. For the case that cj=c, we propose two approximation lgorithms with the asymptotical competitive ratio of3/2and the competitive ratio of a2≈1.54, respectively, where a2is the solution of α₂³-2α₂²+2α2-2=0.In chapter3, we study a supply chain scheduling of three stages. The warehouse in which all of the materials and finished jobs are kept and the machine that processes the jobs are located at different place. The jobs are traveled between the factory and the warehouse. The paper mainly consider two models. One is two vehicles and a single-machine, the other is a vehicle and two parallel machines. The objective is to minimize the makespan of the schedule and the preemption of jobs is not allowed. The worst-case ratios of our algorithms for above two models are proven to be2and (?), respectively.In chapter4, we summarize the full text and give the future research.