An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties
作者机构：School of Mathematical SciencesHebei Normal UniversityShijiazhuang 050024HebeiChina
出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊（英文）)
年 卷 期：2024年第12卷第2期
页 面：495-504页
核心收录：
学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学]
基 金：the National Natural Science Foundation of China(No.11971146) the Natural Science Foundation of Hebei Province of China(Nos.A2019205089 and A2019205092) Hebei Province Foundation for Returnees(No.CL201714) the Graduate Innovation Grant Program of Hebei Normal University(No.CXZZSS2022053)
主 题：Order scheduling Delivery time Submodular rejection penalty Approximation algorithm
摘 要：In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection *** this problem,we are given m dedicated machines in parallel and n customer *** order has a delivery time and consists of m product types and each product type should be manufactured on a dedicated *** order is either rejected,in which case a rejection penalty has to be paid,or accepted and manufactured on the m dedicated *** objective is to find a solution to minimize the sum of the maximum delivery completion time of the accepted orders and the penalty of the rejected orders which is determined by a submodular *** design an LP rounding algorithm with approximation ratio of n+1 for this problem.
维普期刊数据库
