In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection penalties.In this problem,we are given m dedicated machines in parallel and n customer orders.Each o...In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection penalties.In this problem,we are given m dedicated machines in parallel and n customer orders.Each order has a delivery time and consists of m product types and each product type should be manufactured on a dedicated machine.An order is either rejected,in which case a rejection penalty has to be paid,or accepted and manufactured on the m dedicated machines.The 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 function.We design an LP rounding algorithm with approximation ratio of n+1 for this problem.展开更多
Let F denote the folded （2D ＋ 1）-cube with vertex set X and diameter D ≥ 3. Fix x∈ X. We first define a partial order ≤ on X as follows. For y,z ∈ X let y ≤ z whenever （x,y）＋ （y,z） =- （x, z）. Let R ...Let F denote the folded （2D ＋ 1）-cube with vertex set X and diameter D ≥ 3. Fix x∈ X. We first define a partial order ≤ on X as follows. For y,z ∈ X let y ≤ z whenever （x,y）＋ （y,z） =- （x, z）. Let R （resp. L） denote the raising matrix （resp. lowering matrix） of P. Next we show that there exists a certain linear dependency among RL2, LRL, L2R and L for each given Q-polynomial structure of F. Finally, we determine whether the above linear dependency structure gives this poser a uniform structure or strongly uniform structure.展开更多
基金the National Natural Science Foundation of China(No.11971146)the Natural Science Foundation of Hebei Province of China(Nos.A2019205089 and A2019205092)+1 种基金Hebei Province Foundation for Returnees(No.CL201714)the Graduate Innovation Grant Program of Hebei Normal University(No.CXZZSS2022053).
文摘In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection penalties.In this problem,we are given m dedicated machines in parallel and n customer orders.Each order has a delivery time and consists of m product types and each product type should be manufactured on a dedicated machine.An order is either rejected,in which case a rejection penalty has to be paid,or accepted and manufactured on the m dedicated machines.The 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 function.We design an LP rounding algorithm with approximation ratio of n+1 for this problem.
基金Supported by the Natural Science Foundation of China(No.11471097)the Innovative Fund Project of Hebei Province(sj.2017084)
文摘Let F denote the folded （2D ＋ 1）-cube with vertex set X and diameter D ≥ 3. Fix x∈ X. We first define a partial order ≤ on X as follows. For y,z ∈ X let y ≤ z whenever （x,y）＋ （y,z） =- （x, z）. Let R （resp. L） denote the raising matrix （resp. lowering matrix） of P. Next we show that there exists a certain linear dependency among RL2, LRL, L2R and L for each given Q-polynomial structure of F. Finally, we determine whether the above linear dependency structure gives this poser a uniform structure or strongly uniform structure.
