The scheduling of computer and manufacturing systems has been the subject of ex tensive research for sixty years.In addition to computers and manufacturing, scheduling theory can be applied to many areas including agriculture, hospital and transport.Due to its profound significance in both real world and theory, scheduling has always been a hot topic in the research of combinatorial optimization since the 1950s.Supply chain schedul ing is relatively new scheduling model, which are attracting more and more attention of scholars recently.In our research report, many new results of computational complexity and algorithm on the supply chain scheduling problems are presented.In Chapter Ⅰ, we briefly introduce some fundmental knowledge concerned with our work, basic background and research status on the subject.In Chapter Ⅱ, we adldress a supply chain scheduling model with outsourcing and trans portation.In the model, a job can be scheduled either on a single machine at a manufacturers plant or outsourced to a subcontractor.We assume that there are a sufficient number of vehicles at the manufacturer and the subcontractor such that each completed job can be transported to its customer immediately.For a given set of jobs, the decisions we need to make include the selection of jobs to be outsourced and the schedule of all the jobs.For some different objective function problems, we study their conplexity of computation and present their optimal polynomial or dynamic programming algorithms.In Chapter Ⅲ, we consider an assembling manufacture system where several suppliers provide component parts to a manufacturer, who assembles products from all the supplied component parts.The delivery time of any product is the maximum of the suppliers delivery time of the parts needed for that product.We assume that the final stage is non-bottleneck.Chen and Hall (2007) show that the suppliers problem of minimizing the total weightednumber of tardy parts is binary (i.e., weakly) NP-hard, and left an open problem of whether it is unary (i.e., strongly) NP-hard.In this chapter, we resolve this open problem by showing that it is unary NP-hard.Moreover we show that the suppliers problem of minimizing the total late work of parts is also unary NP-hard.In Chapter Ⅳ, we study a coordinated scheduling problem of production and transporta tion in which each job is transported to a single batching machine for further processing.There are m vehicles that transport jobs from the holding area to the batching machine.Each vehicle can transport only one job at a time.The batching machine can process a batch of jobs simultaneously where there is an upper limit on the batch size.Each batch to be processed occurs a processing cost.The problem is to find a joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized.For a special case of the problem where the job assignment to the vehicles is predetermined, Tang L.X.and Gong H.[61] provide a polynomial time algorithm, and the general problem, they prove that it is strongly NP-hard.In this chapter, for the general problem that the number of vehicles m is a variable which is dependent on the size of the input instances, we prove that the problem is strongly NP-hard.In Chapter Ⅴ, we consider a two-stage supply chain scheduling problem in which the first stage is job production and the second stage is job delivery.The focus is on the study of the integration of production scheduling with delivery of finished products to customers.In our considered model each job can be processed on either of two identical machines, and then delivered by a vehicle to a customer location.We present an improved algorithm with the worst-case performance ratio 31/20, which improves the known upper bound of 5/3.In Chapter Ⅵ, we develop a model of distributionally robust generalized assignment problem, where the processing times p(i)j are random variables, instead of constants.The distribution of random variables belongs to a set of multivariate distributions with known first and second moments.Via duality theory of moment problems, the distributionally robust generalized assignment problem can be approximated by tractable semidefinite pro gramming problem.By introducing a randomized rounding algorithm, we get a schedule with expectation of makespan at most T in stochastic sense and cost at most C.