Approximation Algorithm For Scheduling Problem With Release Dates And Delivery Times

Scheduling problems have been studied widely. Someone has been studied scheduling problems with deterioration effects and learning effects,someone has been studied the online process scheduling problems, etc. In this paper, on the actual background of factory machined workpiece(workpiece and task represents the same concept), there are two main objects in our study.The first is a single sequencing problem. Its objective function is related to the task completion time, weight and delivery time. Each task has three factors (release time, processing time, delivery time).This scheduling problem is widely studied.especially the classical algorithms Schrage ruleand Jackson. In this paper.these classical algorithms are extended and improved so that get a new approximation algorithm called WNI algorithm. Then we analyze and studythis approximation algorithm when the processor has no idle time. By analyzing the content and the characteristics of the new approximation algorithm, we estimate the time complexity of the algorithm is O(n2 log n) (n represents the number of jobs).the worst error rate is the constant which greater than 1. The second is a parallel machine scheduling problem, its objective function is only related to the task completion time and delivery time. This scheduling problem is fewer studied. In this paper.Schrage ruleis extended and used to get a approximation algorithm which is called IPS. By calculating the timeof each step of this algorithm to get the time complexity of the algorithm,andby minimal counter example method proves that the worst error rate is 3.