Design And Analysis Of Algorithms On Some Shop Scheduling Problem

This paper studies two kinds of sorting problem models under free-running and flowing-work environment.The core of the research is the approximate algorithm design and the worst-case analysis.The full text is divided into five chapters as follows.The first chapter briefly introduces the basic knowledge of sorting problems and related knowledge of free and running jobs.In the second chapter,we study a sort of free-operation scheduling problem of three ma-chines whose processing time is determined by the speed of the workpiece and the machine.In this problem,the workpiece is first processed on three free-running machines.The work-piece J_j is on the machine The machining time is determined by the workpiece length pj and the machine speed si.The goal is to minimize the maximum completion time,expressed in three parameters as 03|pij =pj/si|Cmax,The condition is not greater than the approximate algorithm of 5/4.In the third chapter,we study a sort of job-flow sorting problem of two machines without waiting for a job and the machine has multi-functional properties.In this problem,the job must first be processed on two flow-line machines.The job J_j A process can not be interrupted in the process,the first machine can process the workpiece J_j two processes.The goal is to minimize the maximum completion time,expressed in terms of three parameters as F2|nwt,mtflx|Cmax,and we improve the results of the existing literature with the worst case 5/3,We design an approximate algorithm with the worst case not more than 13/8.In the fourth chapter,we study a sort of job-flow sorting problem of two machines without waiting for the workpiece to be processed and can be divided,and the machine has multiple functions.In this problem,the workpiece must be processed on two flow-line machines first.The workpiece Jm Two processes can not be interrupted in the process,the first machine can be processed J_j two processes,the second part of the workpiece can be interrupted during processing.The goal is to minimize the maximum completion time,expressed in terms of three parameters as F2|nwt,mtflx,prmp|Cmax,which further extends the existing literature results(the existing literature presents heuristic algorithms),We design an approximate algorithm with the worst case not more than 8/5.The fifth chapter sums up the full text and puts forward the further research direction of the related question.