A Study On Scheduling With Time Restrictions And Some Related Problems

Scheduling has been one of the most classical combinatorial optimization problems for several decades.In recent years,more and more models arise from both the application and the theoretical areas.This thesis investigates scheduling with time restrictions,which has potential applicability to flexible manufacturing systems and printed circuit board assembly,and also it can be seen as a new model with resource constraints.The thesis is divided into four chapters,focusing on design and analysis of approximation algorithms.Chapter 1 gives an introduction on related concepts and the previous reaseach,espetially those known algorithms for classical single or parallel machines scheduling problems.In Chapter 2,single machine scheduling with time restrictions is considered,where it is assumed that at most B jobs can be processed within any one unit time interval.For B=2,an asymptotically optimal algorithm is provided.For B?3,we design another algorithm which always produces a permutation within a factor of 5/4 of the optimum for B?5 and a permutation within a factor of B/(B-1) for B=3,4(plus an additional small constant).Chapter 3 studies two parallel machines scheduling with time restrictions.Both the asymptotic and absolute performance ratios of the classical LS and LPT algorithms are discussed.If B=2,we show the two ratios are 3/2 and 2 for LS,and 1+(1/n) and 5/4 for LPT,respectively.If B?3,the asymptotic performance ratios of LS is (5/2)-(2/B).In Chapter 4,we consider another single machine scheduling problem,where subcontracting options are provided.Suppose each job can either be processed by the in-house machine or be sent to the subcontractor.The production cost on the in-house machine is measured by the number of tardy jobs,while the outsourcing cost is determined by the subcontracted jobs.The problem of minimizing the total cost is NP-hard.We give a pseudo-polynomial time algorithm based on the dynamic programming method.Moreover,if the outsourcing cost is proportional to the total processing time of subcontracted jobs,then an approximation algorithm with worst case analysis is designed.Finnaly,we give some concluding remarks and future research in Chapter 5.