关键词: 单机, 工程调度, 在线, 线性恶化

Abstract: In typical wire rod production lines, the square billets are transported to a heating furnace to be heated to the desired rolling temperature, and then are hot-rolled into wire rods on a rolling machine. However, the rolling time of a square billet on a rolling machine is not a constant value and it relies on its starting temperature. In general, the temperature of the heated square billets drops by degrees, as the waiting time for rolling increases. This results not only inthe wire head being prone to the cracks during the rolling process but also in a longer rolling time, as well as a greater rolling torque and rolling power, leading to large amounts of raw materials and energy consumption. The phenomenon that rolling time of a square billet increases as its waiting time for rolling increases is referred to as “deterioration effect”. In addition, wire orders from customers arrive unexpectedly and remain unexposed until they are placed with the steel plants, which is considered “online over time” or “online” for short in this work. How to schedule the heated square billets from “online” orders in rolling operation in order to mitigate the deterioration effect of square billets has become a crucial issue for wire manufacturers.
In this work, we consider an interesting online scheduling problem on a single machine with linear deterioration effect.Especially, there are irrelevant jobs arriving online over time and the fundamental knowledge of each job J_j, such as its basic processing length b_j, is not revealed for the scheduler until it is released at time r_j. Also, the jobs become available for execution upon their respective release times. The actual processing time P_j of job J_j is assumed to be a linear increasing function of its starting time S_j, i.e., P_j=b_j+KS_j, where K>0. Note that at most one job can be executed on the machine at every point of time and interruption is disallowed. The objective of this scheduling problem is to devise an online schedule algorithm such that the total actual processing time of all jobs is minimized. Studying the online scheduling problem of minimizing the total actual processing time of wire rods with deterioration effects can enable preheated billets to be started as early as possible, avoiding quality issues caused by low-temperature rolling. Moreover, it can minimize the total actual processing time for wire rodes to reduce the resource consumption. Thus, it is of great practical significance for wire manufacturing enterprises.
For this problem, the lower bound is proved to be 2 by means of adversary method. Subsequently, we present an algorithm Delayed Shortest Basic Processing Time (DSBPT) and analyze its several rigid conditions which remain a large obstacle to conducting performance analysis of DSBPT. To make this problem tractable, an auxiliary flexible online algorithm, known as Flexible Delayed Shortest Basic Processing Time (FDSBPT) is designed, which is a flexible version of algorithm DSBPT. Owing to the flexibility of FDSBPT, the performance analysis of FDSBPT becomes easier, and more crucially, FDSBPT may generate several different schedules with respect to an instance, involving the schedule created by the algorithm DSBPT. This indicates that the algorithm DSBPT is a special description of FDSBPT in a particular condition, namely that the competitive ratio of DSBPT is no more than that of FDSBPT. In general, the competitive ratio of an online algorithm is generally achieved in the nondominated instances, and the competitive analysis of online algorithms proceeds more smoothly if the structure of nondominated instances is more regular. In view of this, we apply the novel “peeling onion” analysis technology to seek such nondominated instances with regular structure. Specifically, we choose an instance at random, and adjust progressively this instance to make its structure more regular in the case of a nondecreasing competitive ratio, while removing the dominated instances successively. Based on the nondominated instances with regular structure that we find, we explicitly derive that the algorithm FDSBPT achieves a competitive ratio of 2, which implies that the competitive ratio of DSBPT is also 2. In other word, the algorithm DSBPT is the optimal online algorithm for the problem we investigate.
In the end, combining a numerical example, we can summarize that the algorithm DSBPT can effectively reduce the rolling time in the rolling operation and provide effective decision-making information for wire enterprise managers. The results obtained in this paper are applicable not only for the wire manufacturing enterprises but also for those enterprises in which deterioration effect is included in the actual production process.
In future work, we will consider the online scheduling of multiple rolling furnaces, which is also appealing and worth the effort.

Key words: single machine, project scheduling, online, linear deterioration