Research On Scheduling For Minimizing Total Weighted Completion Time Under Typical Environments

The total weighted completion time of jobs is an important criterion to be optimized in scheduling.We study in this thesis some scheduling problems related to the minimization of the total weighted completion time under several typical machining environments.In Chapter 1,we first introduce some preliminary concepts and terms in combinatorial optimization and scheduling,then we present a review for the problems and research results related to this thesis.In Chapter 2,we study the scheduling problem for minimizing the total weighted completion time under the two-machine flow-shop environment,where the jobs have a common processing time on the second machine.We show that this problem is strongly NP-hard and present a polynomial-time approximation algorithm for this problem with the worst-case performance ratio at most 2?/(?+?),where and ? denote the minimal and maximal processing time of all the operations,respectively.In Chapter 3,We study the scheduling problem for minimizing the total weighted completion time under the environment with coordination of transportation and batching scheduling.In this problem,all jobs and vehicles are initially located at a holding area,and each of the jobs needs to be transported by one of the available vehicles before it can be processed by a single batch machine.The vehicle can transport one job at a time,and the processing time of a batch is a constant independent of the jobs in the batch.In the case that there is just one single vehicle,we show that the problem is strongly NP-hard,answering an open problem posed in the literature.Moreover,we present a polynomial-time3-approximation algorithm when the batch capacity is at least 2.In Chapter 4,we introduce and study the rescheduling problem to tradeoff between the global disruption of original jobs and the scheduling cost of new jobs under the environment with flexibility of original jobs.In this problem,a set of original jobs has been scheduled on the machine but the processing has not been processed.Then a set of new jobs arrives unexpectedly before the processing of the original jobs starts.The manufacturer needs to adjust the existing schedule of the original jobs with a view to obtaining a new schedule containing the new jobs;for the sake of reputation and interest,the design of a schedule needs to consider the global disruption of original jobs and the scheduling cost of new jobs in the same time.Three assumptions in our research are different from that in the literature.(1)We regard the original jobs as a unified whole(a big task),called original task,and study their global disruption.(2)In a schedule,we assume that the original task can be split into small pieces which may control the global disruption efficiently.(3)The cost of the original jobs is calculated by their global disruption,and the cost of the new jobs is calculated by some ordinary scheduling functions.The goal of the rescheduling problem studied in this chapter is to tradeoff between the global disruption of original jobs and the scheduling cost of new jobs,where the scheduling cost functions of the new jobs include the total weighted completion time,the maximum lateness,the total completion time,and the weighted number of tardy jobs.For these problems,complexity results are presented in this chapter.