This paper focuses on the online production scheduling of the steel rolling processes in a single-machine environment with objective to minimize the maximum delivery completion time of all of the jobs, subject to the ...
详细信息
This paper focuses on the online production scheduling of the steel rolling processes in a single-machine environment with objective to minimize the maximum delivery completion time of all of the jobs, subject to the job deterioration effect and non-delayed processing constraint. The deterioration is reflected in the processing time of the job. Specifically, the job's processing time is a linear function of its start time and can be denoted as p(j )= a(j )(A+Bt), where A > 0, B > 0 and a(j) > 0 represents the job's processing deterioration rate. For this problem, we firstly show that the competitive ratio of any deterministic online algorithm is not less than 1+ Ba-max . Then, we design an online algorithm called Modified-Largest Delivery Time (M-LDT) and show the algorithm M-LDT is (1+alpha)(1+ Ba-max)-competitive, where is the positive root of alpha(2) - alpha -1 =0. Finally, we use the combination of graphs and tables to give the simulation results of multiple instances, and then verify the correctness and effectiveness of our proposed online algorithm.
暂无评论