摘要：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

摘要：Online scheduling on identical machines is investigated in the setting where jobs arrive over time. The goal is to minimize the total completion time. A waiting strategy based online algorithm is designed and is proved to be 2.28 -competitive. The result improves the current best online algorithm from the worse-case prospective.

摘要：The overall burst loss probability is the primary metric of interest in an optical burst switching network with sparse wavelength conversion capabilities (SWCC-OBS). With the overall burst loss probability as the optimization objective, one has to solve an integer nonlinear programming (INLP) problem. In order to overcome the computational difficulties, we propose a fictitious play method to approximately solve the INLP. Consequently, a randomized routing strategy can be achieved. The simulation results show that the proposed strategy can give a near-optimal route that avoids the conflict of burst data effectively and decreases the overall burst loss probability. At the same time it also performs well in balancing loads throughout the whole network under different kinds of burst traffic pattern.

摘要：The identical parallel machine scheduling problem with the objective of minimizing total weighted completion time is considered in the online setting where jobs arrive over time. An online algorithm is proposed and is proven to be (2.5−1/2m) -competitive based on the idea of instances reduction. Further computational experiments show the superiority over other algorithms in the average performance.