Benders' cuts guided large neighborhood search for the traveling umpire problem

This article introduces the use of Benders' cuts to guide a large neighborhood search to solve the traveling umpire problem, a sports scheduling problem inspired by the real‐life needs of the officials of a sports league. At each time slot, a greedy matching heuristic is used to construct a schedule. When an infeasibility is recognized first a single step backtracking is tried to resolve the infeasibility. If unsuccessful, Benders' cuts are generated to guide a large neighborhood search to ensure feasibility and to improve the solution. Realizing the inherent symmetry present in the problem, a large family of cuts are generated and their effectiveness is tested. The resulting approach is able to find better solutions to many instances of this problem. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 ‐ ε for any ε > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Batch scheduling on a two‐machine jobshop with machine‐dependent setup times

The problem of minimum makespan on an m machine jobshop with unit execution time (UET) jobs (m ≥ 3) is known to be strongly NP‐hard even with no setup times. We focus in this article on the two‐machine case. We assume UET jobs and consider batching with batch availability and machine‐dependent setup times. We introduce an efficient \begin{align*}(O(\sqrt{n}))\end{align*} algorithm, where n is the number of jobs. We then introduce a heuristic for the multimachine case and demonstrate its efficiency for two interesting instances. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A genetic algorithm with neighborhood search for the resource‐constrained project scheduling problem

The resource‐constrained project scheduling problem (RCPSP) consists of a set of non‐preemptive activities that follow precedence relationship and consume resources. Under the limited amount of the resources, the objective of RCPSP is to find a schedule of the activities to minimize the project makespan. This article presents a new genetic algorithm (GA) by incorporating a local search strategy in GA operators. The local search strategy improves the efficiency of searching the solution space while keeping the randomness of the GA approach. Extensive numerical experiments show that the proposed GA with neighborhood search works well regarding solution quality and computational time compared with existing algorithms in the RCPSP literature, especially for the instances with a large number of activities. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

基于核与灰度的区间灰数多属性群决策方法

针对属性值为区间灰数且专家权重未知、属性权重部分已知的不确定多属性群决策问题,提出了一种基于区间灰数的核和灰度的决策方法。给出了区间灰数的基于核和灰度的简化形式,充分利用区间灰数的核和灰度的信息建立优化模型求得属性的权重。在求出属性权重的基础上,运用灰色关联方法分别求取各专家的核与灰度距理想方案值的关联系数,综合两者得到专家权重,最终综合专家意见并对方案比较排序得出最优结果。鉴于此,提出一种基于区间灰数相对核与灰度的决策方法。最后以一个算例验证该方法的有效性和可行性。     

基于二维量度的复杂设备预防性维修决策优化

针对使用与维修具有两个测量维度的复杂设备,开展了其预防性维修决策的优化研究。基于二维量度的故障模式,给出了二维故障率的定量描述方法;分析了其预防性更换过程的基本过程,探讨了二维量度下更换周期对维修效果的影响,并从经济性角度建立了二维工龄更换费用模型;最后,采用算例的形式,对某设备维修决策同时考虑日历使用时间和行驶里程的情况,进行了二维更换间隔期的优化求解,从而验证了所建立方法与模型的实用性。     

Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015     

A sequential scheduling problem with impatient jobs

There are n customers that need to be served. Customer i will only wait in queue for an exponentially distributed time with rate λ_i before departing the system. The service time of customer i has distribution F_i, and on completion of service of customer i a positive reward r_i is earned. There is a single server and the problem is to choose, after each service completion, which currently in queue customer to serve next so as to maximize the expected total return. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 659–663, 2015     

一种基于区间数的地面防空火力配系评估技术

针对已有评估技术存在的不足,提出了一种基于区间数的地面防空火力配系评估技术。给出了影响防空火力配系的评价指标,建立了权重为区间数的地面防空火力配系综合评价模型,给出了评价其优劣的排序方法。最后通过实例分析验证,该技术评估结果准确,能有效减小误差,对指挥员科学决策具有一定的参考价值。     

Single machine just‐in‐time scheduling problems with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs to be processed and his own objective function, and both share a common processor. In the single‐machine problem studied in this article, the goal is to find a joint schedule that minimizes the total deviation of the job completion times of the first agent from a common due‐date, subject to an upper bound on the maximum deviation of job completion times of the second agent. The problem is shown to be NP‐hard even for a nonrestrictive due‐date, and a pseudopolynomial dynamic program is introduced and tested numerically. For the case of a restrictive due‐date (a sufficiently small due‐date that may restrict the number of early jobs), a faster pseudopolynomial dynamic program is presented. We also study the multiagent case, which is proved to be strongly NP‐hard. A simple heuristic for this case is introduced, which is tested numerically against a lower bound, obtained by extending the dynamic programming algorithm. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 1–16, 2014