Outsourcing And Timing Released Resource Scheduling Problem

In contemporary society,combinatorial optimization problem has become the basic mathematical model to solve the problem of many social life.The scheduling problem is to solve a lot of factories processing problems.And this paper mainly studies the scheduling problem with subcontract processing time and resources.The problem of the approximation algorithms for two-machine flow shop scheduling with an outsourcing option,namely the problem can be divided into two stages,local stage and outsource processing stage,including local machining to put part of the jobs in a local shop,can create a makespan of the in-house stage;And subcontract processing for the rest of the jobs to outsourcers processing,will create a outsoucing total cost,the goal of the problem for minimizing the sum of the makespan of the in-house stage and the total cost of the outsourcing stage.The problem of minimizing the total completion time on a single machine with timing released resource,is a group of the jobs on the single processor,job processing need to consume non-renewable resources,the resources on the single machine has two resources put points,the goal of the problem is minimizing the total completion time.This thesis is divided into four chapters.In Chapter 1,first of all,we give a basic description of combination optimization and scheduling problems,and introduces the basic definition and contents of the approximate algorithm,as well as some issues,the related research results in this paper.In Chapter 2,we study the research of the approximation algorithms for two-machine flow shop scheduling with an outsourcing option problem,which is divided into to outsourcing two machine flow shop scheduling,outsourcing two machine ordered flow shop scheduling and outsourcing two machine open shop scheduling,and gives the approximate algorithms and worst cases for 2,3/2and3/2,respectively.In Chapter 3,we study the problem of minimizing the total completion times on a single machine with timing released resource,and analyzed the complexity,presents a worst case bound for 9/7 of the approximate algorithm.Finally,we give some concluding remarks and the further research in Chapter 4.