A Class Of Scheduling Problems With Release Dates And Delivery Times

Scheduling was first proposed in the machinery manufacturing industry, usually defined as the jobs were machined on one or multiple machines, through the adjustment of the jobs machining sequence, so that the processing job is completed as soon as possible, to improve the efficiency of the machine, etc.This article mainly considers the practical problems which were pulled out in the factory. The first, single machine problem, that is, how to adjust the order if there is only one processor to process jobs, in order to achieve the purpose of processing jobs to complete as soon as possible. We introduce the Jackson algorithm and expand it to get new algorithm H and N, at the same time, give N.s worst-case performance and the time complexity, also prove that the delay problem is NP-hard.The second, parallel machine problems, how to adjust the processing sequence if there are many processors of the same type with irrelevant to achieve the completion quickly. In this article, we mainly use Jackson algorithm in parallel machine environment and improve the algorithm to obtain new algorithms PJS, we analyzed and discussed the worst error ratio and time complexity of PJS. Also discussed the situation with respect to the work can be split, and get PPJS algorithm also give the time complexity.