Improvement Of Ordinal Semi-online Scheduling Algorithm

In this paper,we mainly discuss the scheduling problem of workpieces with similar processing time on the same machine.We stipulate that n independent workpieces J1,J2,…,Jn are processed on m machines M1,M2,…,Mm with the same performance,and each workpiece can only be machined once on a machine.In order to facilitate the study of this paper,later studies do not take into account the arrival time of the workpiece,and let each workpiece is arranged in a non-incremental order of processing time.Use pi to represent the processing time of Ji,then p1? p2?…?pn.This article improves the new algorithm based on the Pm algorithm obtained by Wei-Ping Liu,Jeffrey B.Sidney and Andre van Vliet in 1996([1]).The new algorithm specifies that each arrived artifact is ordered by serial number and sent to a specific machine in turn.Each task can be processed by one processor at a time and that a processor is capable of processing at most one task at a time.This algorithm is named as PmD algorithm.We record the completion time of the last workpiece is recorded as the total completion time,and the objective function of this scheduling problem is to minimize the total completion time This paper obtains and proves that the worst performance ratio is better than that of the Pm algorithm when the number of machines is m=2 or m=3This thesis is composed of four chapters.The first chapter is the introduc-tion,which mainly introduces combinatorial optimization problems.It focuses on a classic sorting problem under the combinatorial optimization problem,and details in the background and classification of the ranking problems.And multiple methods of solving the optimization problem.Since this paper is an improved PmD algorithm based on Pm algorithm,the Pm algorithm and the PmD algorithm are described in detailThe second chapter and the third chapter respectively prove the worst per-formance ratio of two machines and three machines under the PmD algorithm.The PmD algorithm is an improved algorithm based on the Pm algorithm.The Pm algorithm has been proven to be m=2,m=3,and the upper bound of the worst performance ratio is 4/3,7/5.In this paper,under the condition of controlling the processing time of any workpiece of 1?pj?r(r?1),the worst performance ratio we get is significantly better than the Pm algorithm.The fourth chapter is a summary of this paper.Due to space limitations,the worst performance ratio of PmD algorithm on any machine is not studied.At the end of this paper,some suggestions on what can be done are also given.