Approximate solution of a profit maximization constrained virtual business planning problem

A virtual business problem is studied, in which a company-contractor outsources production to specialized subcontractors. Finances of the contractor and resource capacities of subcontractors are limited. The objective is to select subcontractors and distribute a part of the demanded production among them so that the profit of the contractor is maximized. A generalization of the knapsack problem, called Knapsack-of-Knapsacks (K-of-K), is used to model this situation, in which items have to be packed into small knapsacks and small knapsacks have to be packed into a large knapsack. A fully polynomial time approximation scheme is developed to solve the problem K-of-K.     

服务多类需求串行供应链的最优控制策略

研究由一系列生产环节采用串行方式组成多级供应链的最优控制策略.在此供应链中,原材料经过各级生产环节顺序加工形成最终产品.各级生产环节的加工时间服从随机分布.对最终产品存在多类随机需求.在每个时刻,管理者需要决定:1)是否该启动某个生产环节的生产;2)当有需求到达时,是否该满足此需求.管理者期望系统运行的总期望折扣成本最小.构造了该系统的马尔可夫决策模型并深入研究了其最优控制策略及其动态协同特性.在生产策略方面,证明系统的最优生产策略就是对各级生产环节采用动态的基本库存策略.该策略的动态协同特性主要体现在各级生产环节的最优基本库存水平受其他生产环节的库存水平影响.在产品分配方面,证明系统的最优分配策略是动态配给策略.该策略的动态协同特性主要体现在每类随机需求最优配给水平受各级生产环节的库存水平影响.     

Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns

We give polynomial time algorithms for a job scheduling problem. By duality we transform a special case of the drug market crackdown schedulingproblem to the above job scheduling problem and thus derive polynomial timealgorithms to the second problem. Finally, using the algorithm for the specialcase, we develop a quasipolynomial time approximation algorithm for thegeneral case of the drug market crackdown scheduling problem with monomialcost functions.