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

IEEE Access

Zailin Guan¹  Yarong Chen¹  Fuh-Der Chou²  Ya-Chih Tsai³ 

[1] College of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, China;College of Mechanical and Electrical Engineering, Wenzhou University, Zhejiang, Wenzhou, China;Department of Hotel Management, Vanung University, Taoyuan, Taiwan;

关键词: Heuristic algorithm;    mixed integer linear programming model;    single-machine scheduling;    weight-modifying activity;   

DOI  :  10.1109/ACCESS.2022.3170734

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown