华中科技大学学报（自然科学版）2025，Vol.53Issue(10)：36-41,6.DOI:10.13245/j.hust.251097
带权重和次模惩罚费用的平行机客户订单调度问题
Parallel-machine customer order scheduling with weighted and submodular rejection penalties
摘要
Abstract
The problem of parallel-machine customer order scheduling with weighted and submodular rejection penalties was addressed.Given m dedicated parallel machines and n customer orders,each order consisted of m types of products,and each machine could process only one type of product.Each customer order could either be accepted,requiring all types of products in the order to be processed using the m machines,or rejected,incurring a certain penalty cost.The weighted completion time of an accepted order was defined as the product of the order's weight and its completion time,where the completion time was determined by the time when the last product in the order was finished.It was asked to find a set of accepted orders A and a set of rejected orders R so that the sum of the maximum weighted completion time of accepted orders and the penalty cost of rejected orders was minimized,where the penalty cost was determined by a submodular function.Based on Lovász's rounding technique,a 2-approximation algorithm was proposed.Experiment results show that the solutions produced by our algorithm are superior to its theoretical performance,and the algorithm maintains strong applicability as the data size increases.关键词
客户订单调度/次模函数/Lovász舍入技术/近似算法Key words
customer order scheduling/submodular function/Lovász rounding technique/approximation algorithm分类
数理科学引用本文复制引用
王文成,郑希雅,刘晓非..带权重和次模惩罚费用的平行机客户订单调度问题[J].华中科技大学学报（自然科学版）,2025,53(10):36-41,6.基金项目
云南省基础研究计划面上项目(202501AT070360) （202501AT070360）
云南省智能系统与计算重点实验室开放课题资助项目(ISC24Y01) （ISC24Y01）
云南省教育厅科学研究基金资助项目(2024J0573,2025Y0149) （2024J0573,2025Y0149）
云南大学专业学位研究生实践创新基金资助项目(ZC-242410696). （ZC-242410696）
