关键词: 混合批处理调度, 拒绝成本, 动态规划算法, 时间复杂度

Abstract: A vacuum heat treatment furnace is an innovative and environmentally friendly heat treatment technology that combines heat treatment with vacuum technology. It is widely used in the manufacturing processes of high-end metal components such as molds, fasteners, and precision coupling parts. It is primarily applied in industries such as automotive, high-speed railways, nuclear power, aerospace, and aviation. In comparison to other processes, vacuum heat treatment has a longer processing time. After vacuum treatment process, the metal components exhibit high quality and extended lifespan. Due to high purchased cost and restricted installation space, the number of vacuum heat treatment furnaces is limited, and the furnace is the bottleneck machine in real production. When facing production anomalies such as machine failures or urgent rush orders, a common approach is to use rescheduling methods to quickly restore production. However, if the production anomalies exceed a certain critical threshold, rescheduling strategies may be ineffective. By borrowing the concept of “sacrificing a knight to get the king”, it becomes necessary to reject a portion of jobs to ensure the on-time delivery of the accepted ones.
The scheduling of vacuum heat treatment furnace is modeled as mixed batch model. Multiple jobs can be processed on the mixed batch machine simultaneously. When the number of jobs processed in a mixed batch is arbitrary, we call this model as unbounded. The processing time of a mixed batch is the weighted sum of the maximum processing time in the batch and the sum of the processing times for all the job in the same batch. The mixed batch model combines the parallel batch model and serial batch model, which increase the complexity of the mixed batch scheduling problem. In addition, different job release times usually lead to the reduction of utilization of furnaces, and thus it is necessary to reject some jobs. To enhance the utilization of vacuum heat treatment furnaces, the rejection of jobs with low cost-effectiveness is considered. This paper studies unbounded mixed batch scheduling with release dates and rejection, where jobs are either accepted for processing or rejected by paying rejection cost. The makespan and total rejection cost are considered as the objectives in this paper.
Rejecting jobs usually reduce the makespan of furnaces and increase the total rejection cost, and thus it is important to decide the rejected jobs and schedule the accepted jobs. In order to balance the makespan and the total rejection cost, this paper studies three models: the linear weighted model, the constrained model and the Pareto optimization model. The first model is a linear weighted model where objective function is a linear combination of the makespan and the total rejection cost. Based on whether the job is accepted or rejected and its contribution to the objective function, four scenarios have been considered for discussion. A dynamic programming algorithm is designed, and the time complexity of the algorithm is analyzed. The second model is the constrained model, where the total rejection cost or the makespan does not exceed a certain threshold value, and the other objective function is minimized. A dynamic programming algorithm is proposed and its time complexity is analyzed. The third model is Pareto optimization model. The iterative process involves repeatedly constraining the total rejection cost to a certain threshold value and then optimizing the makespan. Based on the analysis of the four scenarios, a dynamic programming algorithm is yielded. After iteration times, the Pareto frontier can be obtained. Lastly, the time complexity of the algorithm is presented.
The insights derived from unbounded mixed batch scheduling with release dates and rejection are as follows. When jobs concentrate on their arrivals during specific time periods, it is possible to achieve line balancing by rejecting certain jobs strategically to optimize the workload on various lines. Jobs with specific arrival times result in more constraints when grouping them for processing. Changes in orders or urgent insertions can reduce the flexibility of scheduling. Rejecting some jobs strategically can alleviate production bottlenecks and enhance the overall flexibility of the scheduling scheme. Taking the advantage over the production flexibility arising from job rejection, a more accurate and scientific schedule can be devised for customers with jobs having different arrival times. This allows for the implementation of differentiated custom services, ultimately enhancing customer satisfaction. These insights highlight the importance of adaptability and strategic decision-making in the face of dynamic production scenarios, emphasizing the potential benefits of rejecting certain jobs to optimize overall system performance and meet customer expectations more effectively.

Key words: mixed batch scheduling, rejection cost, dynamic algorithm, time complexity