Narrow Results

With the popularization of energy conservation and emission reduction, amounts of industrial production has taken energy conservation as a goal to achieve. The paper considers an online parallel-batch scheduling problem with deteriorating and incompatible families on identical machines to minimize the makespan, which minimizes the maximum energy consumption of machines. Specifically, the processing time of job $J_j$ is defined by an increasing function of its starting time $t$, i.e., $p_j={\alpha }_j(A+Bt)$, where ${\alpha }_j>0$ is the deterioration rate of job $J_j$. For the problem, we propose an online algorithm with a competitive ratio of $2+B{\alpha }_{max}$, where ${\alpha }_{max}$ is the largest deterioration rate in an instance. Furthermore, the paper presents a concise computational study of the numerical experiment to show that our algorithm performs very well in practice of this model.

In this paper, we consider an online order scheduling problem with the same order size on two identical machines. The objective is to minimize the makespan. An order list $O=(O_1,O_2,\dots ,O_b)$ is given, where $b$ is a positive integer. For the problem under study, we assume that $b\ge B$ ($B=2,3,4,\dots$), that is to say, at least $B$ orders arrive. A lower bound $\frac{B+2}{B+1}$ for $b\ge B$ is obtained. Also, we design two optimal algorithms $A_1$ and $A_2$ for $B=2m$ and $B=2m+1$ ($m=1,2,3,\dots$), respectively.