This paper proposes a novel chronically evaluated highest instantaneous priority next processor scheduling algorithm. The currently existing algorithms like first come first serve, shortest job first, round-robin, sho...This paper proposes a novel chronically evaluated highest instantaneous priority next processor scheduling algorithm. The currently existing algorithms like first come first serve, shortest job first, round-robin, shortest remaining time first, highest response ratio next and varying response ratio priority algorithm have some problems associated with them. Some of them can lead to endless waiting or starvation and some of them like round-robin has problem of too many context switches and high waiting time associated with them. In the proposed algorithm, we have taken care of all such problems. As the novel algorithm is capable of achieving as good results as shortest remaining time first algorithm and also it will never lead to starvation.展开更多
Considering the complex constraint between operations in nonstandard job shop scheduling problem （NJSSP）, critical path of job manufacturing tree is determined according to priority scheduling function constructed. ...Considering the complex constraint between operations in nonstandard job shop scheduling problem （NJSSP）, critical path of job manufacturing tree is determined according to priority scheduling function constructed. Operations are divided into dependent operations and independent operations with the idea of subsection, and corresponding scheduling strategy is put forward according to operation characteristic in the segment and the complementarities of identical function machines. Forward greedy rule is adopted mainly for dependent operations to make operations arranged in the right position of machine selected, then each operation can be processed as early as possible, and the total processing time of job can be shortened as much as possible. For independent operations optimum scheduling rule is adopted mainly, the inserting position of operations will be determined according to the gap that the processing time of operations is subtracted from idle time of machine, and the operation will be inserted in the position with minimal gap. Experiments show, under the same conditions, the result that operations are scheduled according to the object function constructed, and the scheduling strategy adopted is better than the result that operations are scheduled according to efficiency scheduling algorithm.展开更多
文摘This paper proposes a novel chronically evaluated highest instantaneous priority next processor scheduling algorithm. The currently existing algorithms like first come first serve, shortest job first, round-robin, shortest remaining time first, highest response ratio next and varying response ratio priority algorithm have some problems associated with them. Some of them can lead to endless waiting or starvation and some of them like round-robin has problem of too many context switches and high waiting time associated with them. In the proposed algorithm, we have taken care of all such problems. As the novel algorithm is capable of achieving as good results as shortest remaining time first algorithm and also it will never lead to starvation.
基金National Natural Science Foundation of China(No. 50575062)Natural Science Foundation of Heilongjiang Province,China (No. F200608)+2 种基金Key Project of Scientific Research Subsidy of Abroad Scholars of Heilongjiang Provincial Education Department, China (No.1152hq08)Scientific Research Fund of Heilongjiang Provincial Education Department, China (No.10551z0008)Harbin Municipal Key Project of Science and Technology, China (No.2005AA1CG061-11).
文摘Considering the complex constraint between operations in nonstandard job shop scheduling problem （NJSSP）, critical path of job manufacturing tree is determined according to priority scheduling function constructed. Operations are divided into dependent operations and independent operations with the idea of subsection, and corresponding scheduling strategy is put forward according to operation characteristic in the segment and the complementarities of identical function machines. Forward greedy rule is adopted mainly for dependent operations to make operations arranged in the right position of machine selected, then each operation can be processed as early as possible, and the total processing time of job can be shortened as much as possible. For independent operations optimum scheduling rule is adopted mainly, the inserting position of operations will be determined according to the gap that the processing time of operations is subtracted from idle time of machine, and the operation will be inserted in the position with minimal gap. Experiments show, under the same conditions, the result that operations are scheduled according to the object function constructed, and the scheduling strategy adopted is better than the result that operations are scheduled according to efficiency scheduling algorithm.
