摘要：Abstract: We revisit the classical online scheduling problem on parallel machines for minimizing total weighted completion time. In the problem, a set of independent jobs arriving online over time has to be scheduled on identical machines, where the information of each job including its processing time and weight is not known in advance. The goal is to minimize the total weighted completion time of the jobs. For this problem, we propose an improved 2: 11-competitive online algorithm based on a kind of waiting strategy.​

摘要：针对带有爽约的预约调度问题, 在假定未爽约病人都在相应预约段的起始点准时到达的情况下, 构建了一个以预约人数为优化变量的整数规划模型. 目标函数包括服务病人收益、病人等待费用及系统超时费用. 通过松弛各时间段剩余人数概率的关联约束, 提出了基于拉格朗日松弛的求解算法, 其松弛问题通过动态规划求解, 对偶问题通过经典的次梯度法求解. 数值实验表明, 针对小规模的预约段数时, 该算法都能找到最优解; 当预约段数较大时, 算法找到的最好解整体上优于文献中已有的算法, 从而验证了算法的有效性.

摘要：In this paper, we study the online scheduling of linear deteriorating jobs on a single machine to minimize the total weighted completion time. In the problem, a set of n independent linear deteriorating jobs arriving online over time has to be scheduled on a single machine, where the information of each job including its processing time and weight is unknown in advance. Linear deterioration means that the processing time pj of a job Jj is a linear function of its starting time sj . In this paper, we assume that pj=αj(A+Bsj) , where A and B are non negative with A+B>0 and αj≥0 is the deterioration rate of Jj . The goal is to minimize the total weighted completion time, i.e., ∑wjCj . For this problem, we provide a best possible online algorithm with a competitive ratio of 1+λ(A)+αmaxB , where αmax=max1≤j≤nαj and λ(A)=0 or λ(A)=1 depending on A=0 or A>0