自由作业的供应链排序研究

研究一类集成工件加工和发送的供应链排序模型,即研究如何安排工件在自由作业机器上加工,把加工完毕的工件分批发送给下游客户,使得含生产排序费用和发送费用的目标函数最优.这里,分别取工件最大送到时间和平均送到时间为生产排序费用;而发送费用是由固定费用和与运输路径有关的变化费用组成.利用排序理论和动态规划方法,构造了自由作业供应链排序问题的多项式时间近似算法,并分析算法的性能比.     

自由作业环境下的供应链排序问题

本文研究自由作业环境下的供应链排序问题,研究供应链的上游如何安排工件在自由作业机器上加工,把加工完毕的工件分批发送给下游,使得生产排序费用和发送费用总和最少.这里,生产排序费用是用工件送到时间的函数来表示;发送费用是由发送的固定费用和与运输路径有关的变化费用所组成.本文研究以工件最大送到时间为生产排序费用的自由作业供应链排序问题,在指出问题的NP困难性后,用动态规划算法构造多项式时间近似算法,并分析算法的性能比.本文最后还对特殊情形进行了讨论.     

一类自由作业供应链排序的研究

本文研究一类集成工件生产和发送的排序模型.在该模型中,供应链的上游首先将工件安排在自由作业机器上加工,然后把加工完毕的工件分批发送给下游.问题是寻找生产和发送相连的排序,使得生产排序费用和发送费用总和最少.这里,生产排序费用是以工件带权送到时间和表示;发送费用由固定费用和与运输路径有关的变化费用组成.在指出问题的NP困难性后,本文用动态规划算法构造了一致条件下的多项式时间近似算法,并分析算法的性能比.本文最后还讨论了该问题的其它情形.     

具有可变配送费用和固定配送时刻的单机排序问题

研究了单机环境下生产与配送的协同排序问题.有多个工件需要在一台机器上进行加工,加工完的工件需要分批配送到一个客户.每批工件只能在固定的几个配送时刻出发,不同的配送时刻对应着不同的配送费用.我们的目标是找到生产与配送的协同排序,极小化排序的时间费用与配送费用的加权和.研究了排序理论中主要的四个目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对于配送费用单调非增的情况给出了它们的最优算法.     

平行机的供应链排序

研究平行机环境下的供应链排序,即研究如何安排工件在平行机上加工,把加工完毕的工件分批发送给下游客户,使得生产排序费用和发送费用总和最少。这里,生产排序费用是用工件送到时间的函数表示;发送费用是由固定费用和与运输路径有关的可变费用两部分组成。研究以工件带权送到时间和作为生产排序费用的供应链排序问题,给出多项式时间近似算法,并分析算法性能比。     

基于辅助信息的分层排序集抽样及调查费用分析

辅助信息在改进和完善抽样设计、提高抽样估计精度和节省抽样费用等方面具有重要作用,鉴于此,基于分层排序集样本建立了总体均值的比率估计量,同时考虑估计精度和调查费用两个方面,证明了抽样方案的优良性.最后,通过实例进一步分析,结果表明,在给定的估计精度下,分层排序集抽样方法可以有效降低抽样调查费用.     

基于辅助信息的分层排序集抽样及调查费用分析北大核心

辅助信息在改进和完善抽样设计、提高抽样估计精度和节省抽样费用等方面具有重要作用,鉴于此,基于分层排序集样本建立了总体均值的比率估计量,同时考虑估计精度和调查费用两个方面,证明了抽样方案的优良性.最后,通过实例进一步分析,结果表明,在给定的估计精度下,分层排序集抽样方法可以有效降低抽样调查费用.     

具有不同生产时区费用的单机可拒绝排序问题

考虑了单机环境下,机器具有不同的生产时区费用,并且工件的加工是可以拒绝的排序问题.需要选择要加工的工件集合,对每个加工的工件指派相应的生产区间并排序,并支付拒绝加工工件的拒绝费用.对于排序理论中主要的四个目标函数,研究了单位区间的生产费用随着时间的推迟是单调非增的情况,分析了问题的复杂性,对于这些问题给出了它们的最优算法.     

一类博弈排序问题的纳什均衡存在性证明

研究机器带有激活费用的博弈排序问题. 机器集由两类组成: 一类是速度为1、 激活费用为B的k_1台同型机; 另一类是速度为a(>1)、激活费用为aB的k_2台同型机, 其中k_1与k_2是任意正整数. 工件作为``局中人", 其目的是极小化自身的费用, 工件的费用是由其所在机器的负载和其所承担的激活费用组成, 其中工件承担的激活费用与工件的加工时间成正比. 针对不同的情况, 设计不同的算法, 并证明各算法得到的排序都是纳什均衡.     

单机上的排序与转包问题

本文研究工件排序与转包相连的决策问题,即工件既可以在一制造商的单机上加工,亦可以转包给承包商加工.制造商需要确定哪些工件由自己加工,哪些工件需要转包,及确定所有工件的排序,以极小化排序目标、加工费用与转包费用和.根据承包商机器数量,本文研究了两类模型.对每类模型,证明NP困难性并设计动态规划算法.     

Common due window size and location determination in a single machine scheduling problem

We consider a single machine static and deterministic scheduling problem in which jobs have a common due window. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The objective is to find the optimal size and location of the window as well as an optimal sequence to minimise a cost function based on earliness, tardiness, window size, and window location. We propose an O(n log n) algorithm to solve the problem.     

公共交货期窗口的提前／延期惩罚

本讨论n个独立工件在一台机器上加工,而且加工时间服从正态分布的公共交货期窗口的提前/延期惩罚问题,在确定公共交货期窗口情况下,推导出工件的最优排序具有V型特征。     

Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a combinatorial optimization problem. It deals with route planning and the distribution of goods from a depot to geographically dispersed customers by a fleet of vehicles with constrained capacities. The customers’ demands are known and each customer has a time window in which it has to be supplied. The time windows are assumed to be soft, that means, violations of the time windows are allowed, but associated with penalties. The problem is to organize the vehicle routes optimally, i.e. to minimize the total costs, consisting of the number of used vehicles and the total distance, and the penalties simultaneously. Thus, the problem is formulated as a bicriterion minimization problem and heuristic methods are used to calculate approximations of the Pareto optimal solutions. Experimental results show that in certain cases the allowance of penalties leads to significant savings of the total costs.     

准时生产和宽容交货中的排序问题

本文综述了近年来国内外对宽容交货中排序问题的研究．     

Determination of common due window location in a single machine scheduling problem

We consider the static deterministic single machine scheduling problem in which all jobs have a common due window. Jobs that are completed within the window incur no penalty. The objective is to find the optimal sequence and the optimal common due window location given that the due window size is a problem parameter such that the weighted sum of earliness, tardiness, and due window location penalties is minimized. We propose an O(n log n) algorithm to solve the problem. We also consider two special cases for which simple solutions can be obtained.     

On scheduling around large restrictive common due windows

This paper deals with the problem of scheduling a number of jobs on a single machine around a large, restrictive common due window. We consider individual earliness and tardiness penalties for the jobs. The objective is to find an optimal schedule which jointly minimizes the sum of the earliness and tardiness penalties. This problem is intractable and hence no efficient procedure for solving large instances is expected to be found. For this reason we first introduced a mapping of the problem which takes advantage of the structural properties inherent to optimal solutions. Secondly we solved the problem under study by using this mapping and applying three meta-heuristics, namely evolutionary strategy, simulated annealing and threshold accepting. To validate the quality of these approaches, altogether 250 benchmark problems with different window sizes and positions of up to 200 jobs are examined. Furthermore small instances are solved to optimality by a mixed integer programming formulation.     

基于遗传算法的物流配送车辆调度问题研究

研究使用遗传算法求解物流配送组织过程中车辆调度问题 .通过把时间窗约束和车辆容量约束转嫁到最小费用目标函数中去 ,建立适合于遗传算法的车辆调度模型 .阐述放回式随机复制算子和适应度函数 ,设计描述行驶线路的染色体结构、初始群体生成方法、独特的交叉算子和交换变异算子 ,构造完整的遗传算法 .并给出算例 ,验证调度模型和遗传算法 .     

A uniform framework for the combination of penalties in generalized structured models

Penalized estimation has become an established tool for regularization and model selection in regression models. A variety of penalties with specific features are available and effective algorithms for specific penalties have been proposed. But not much is available to fit models with a combination of different penalties. When modeling the rent data of Munich as in our application, various types of predictors call for a combination of a Ridge, a group Lasso and a Lasso-type penalty within one model. We propose to approximate penalties that are (semi-)norms of scalar linear transformations of the coefficient vector in generalized structured models—such that penalties of various kinds can be combined in one model. The approach is very general such that the Lasso, the fused Lasso, the Ridge, the smoothly clipped absolute deviation penalty, the elastic net and many more penalties are embedded. The computation is based on conventional penalized iteratively re-weighted least squares algorithms and hence, easy to implement. New penalties can be incorporated quickly. The approach is extended to penalties with vector based arguments. There are several possibilities to choose the penalty parameter(s). A software implementation is available. Some illustrative examples show promising results.     

A Two-Stage Group Testing Model for Infections with Window Periods

We present a two-stage group testing model for the detection of viruses in blood samples in the presence of random window periods. As usual, if a tested group is found to be positive, all its members are treated individually. The groups that were tested negative return for a second round after a certain time, new blood samples are taken and tested after pooling. The given system parameters are the size of the population to be screened, the incidence rates of the infections, the probability distributions of the lengths of the window periods, and the costs of group tests. The objective is to minimize the expected cost of running the system, which is composed of the cost of the conducted group tests and penalties on delayed test results and on misclassifications (noninfected persons declared to be positive and, more importantly, persons whose infections have not been identified). By an appropriate choice of the group size and the waiting time for the second round of testings one wants to optimize the various trade-offs involved. We derive in closed form all the probabilistic quantities occurring in the objective function and the constraints. Several numerical examples are given. The model is also extended to the case of several types of viruses with different window periods.     

Simple Heuristics for the Vehicle Routeing Problem with Soft Time Windows

We describe three simple heuristics for the vehicle routeing problem with customer time windows that can be violated by paying appropriate penalties. The customer demands are known, and a homogeneous fleet of vehicles stationed at a single depot is considered. The penalty payable to a customer is assumed to be a linear function of the amount of time window violation. Upper limits are imposed on both the penalty payable and the waiting time allowed at any customer. At each customer in a route, the PC-based heuristics simultaneously determine the actual time to begin service, and the next customer to serve. To achieve this, each heuristic uses different measures to compare the cost of waiting and penalty payable, with the benefit obtained by leaving immediately for the next customer. Computational results on a set of benchmark problems show that the procedure is efficient and enables significant reduction in the number of vehicles required and/or the total route distances while controlling both customer penalties and waiting times.