Single Machine Scheduling Problem With a Weight-Modifying-Activity to Minimize the Total Weighted Completion Time

Abstract

The single-machine scheduling problem with a weight-modifying-activity (WMA) to minimize the total weighted completion time was initially addressed by Mosheiov and Oron in 2020, where the activity was an option, and once the activity was performed, the weights of the subsequent jobs become decreased. This problem has proven to be NP-hard. Following their study, we propose two mixed integer linear programming models (model_1 and model_2). Based on some optimality properties, a heuristic algorithm with swap and insert procedures is developed. The computation results indicate that model_2 can optimally solve problems of up to 40 jobs efficiently, while the average relative percentage of error and hit rate of the proposed heuristic is 0.0005% and 98.2%, respectively. The influence of parameters, such as the number of jobs, the adjusted coefficient for the job weight, and the time of the WMA, on the performance of the proposed methods, are also analyzed.

Keywords

• Heuristic algorithm
• mixed integer linear programming model
• single-machine scheduling
• weight-modifying activity