The combination of online or semi-online with deterioration jobs has never been researched in scheduling problems.In this paper, two semi-online parallel machine scheduling problems with linear deterioration processing time are considered.In the first problem, it is assumed that the deterioration rates of jobs are known in an interval, that is, bj ∈ [0, α], where 0 ＜ α ≤ 1 and bj denotes the linear deterioration rate. In the second problem, it is assumed that the largest deterioration rate of jobs is known in advance, that is, bmax = max1≤j≤n{bj}. For each of the two problems, a heuristic MBLS algorithm is worked out and its worst-case ratio is analyzed. At the same time, the worst-case ratio of the list (LS) algorithm is investigated and it is proved that all the ratios are tight.
展开▼
