On the usage of Lagrangean Relaxation for the convoy movement problem

The problem of routing military convoys between specific origin and destination pairs is known as convoy movement problem (CMP). In this study, we consider an existing mathematical model of CMP and propose a lower bounding procedure based on Lagrangean Relaxation. The robustness of the proposed procedure is evaluated on a variety of test problem instances. Encouraging results are obtained.     

Analysis of algorithms for an online version of the convoy movement problem

In the convoy movement problem (CMP), a set of convoys must be routed from specified origins to destinations in a transportation network, represented by an undirected graph. Two convoys may not cross each other on the same edge while travelling in opposing directions, a restriction referred to as blocking. However, convoys are permitted to follow each other on the same edge, with a specified headway separating them, but no overtaking is permitted. Further, the convoys to be routed are distinguished based on their length. Particle convoys have zero length and are permitted to traverse an edge simultaneously, whereas convoys with non-zero length have to follow each other, observing a headway. The objective is to minimize the total time taken by convoys to travel from their origins to their destinations, given the travel constraints on the edges. We consider an online version of the CMP where convoy demands arise dynamically over time. For the special case of particle convoys, we present an algorithm that has a competitive ratio of 3 in the worst case and (5/2) on average. For the particle convoy problem, we also present an alternate, randomized algorithm that provides a competitive ratio of (√13?1). We then extend the results to the case of convoys with length, which leads to an algorithm with an O(T+CL) competitive ratio, where T={Max _e t(e)}/{Min _e t(e)}, C is the maximum congestion (the number of distinct convoy origin–destination pairs that use any edge e) and L={Max _c L(c)}/{Min _c L(c)}; here L(c)>0 represents the time-headway to be observed by any convoy that follows c and t(e) represents the travel time for a convoy c on edge e.     

Problem difficulty of real instances of convoy planning

Moving men and materials in large numbers and quantities is a long-standing military problem faced by all arms. An important part of this is the routing of convoys so that they reach their correct destinations in the shortest time. The optimization problem at the heart of this problem is referred to as the convoy movement problem. Previous work on the convoy movement problem has made the assumption that the problem is difficult in practice because of the NP-hardness of the problem in combination with the limited success of early approaches based on genetic algorithms. As a result subsequent work has focused on mathematical programming-based methods, principally Lagrangian relaxation. In this paper, we demonstrate that a straightforward reformulation of the problem renders the real-world like instances, used to benchmark previous approaches, amenable to solution by simple heuristics. The main lessons learnt from this work is that analysis of the problem in conjunction with simple algorithms can, in practice, yield surprisingly effective solutions.     

Cost effective scheduling of imperfect inspections in systems with hidden failures and rescue possibility

Motivated by real-world critical applications such as aircraft, medical devices, and military systems, this paper models non-repairable systems subject to a delay-time failure process involving hidden and fatal failures in two stages during their missions. A hidden failure cannot cause the system to stop functioning while a fatal failure causes the entire system loss. The system undergoes scheduled inspections for detecting the hidden failure. In the case of a positive inspection result, the system main mission is aborted and a rescue operation is started to mitigate the risk of the entire system loss. The inspections are imperfect and may produce false positive and negative failures. We propose probabilistic models for evaluating performance metrics of the system considered, including mission success probability, system survival probability, expected number of inspections during the mission, and total expected losses. Based on the evaluation models, we formulate and solve an optimization problem of finding the optimal inspection schedule on a fixed mission time horizon to minimize the total expected loss. Examples are provided to demonstrate the proposed methodology and effects of key system parameters on system performance and optimization solutions.     

Computational complexity of convoy movement planning problems

Convoy movement planning problems arise in a number of important logistical contexts, including military planning, railroad optimization and automated guided vehicle routing. In the convoy movement problem (CMP), a set of convoys, with specified origins and destinations, are to be routed with the objective of minimizing either makespan or total flow time, while observing a number of side constraints. This paper characterizes the computational complexity of several restricted classes of CMPs. The principal objective is to identify the most parsimonious set of problem features that make the CMP intractable. A polynomial-time algorithm is provided for the single criterion two-convoy movement problem. The performance of a simple prioritization–idling approximation algorithm is also analyzed for the K-convoy movement problem. Error bounds are developed for the makespan and flow time objectives.     

Some single-machine scheduling with sum-of-processing-time-based and job-position-based processing times

The single-machine scheduling problems with position and sum-of-processing-time based processing times are considered. The actual processing time of a job is defined by function of its scheduled position and total normal processing time of jobs in front of it in the sequence. We provide optimal solutions in polynomial time for some special cases of the makespan minimization and the total completion time minimization. We also show that an optimal schedule to be a V-shaped schedule in terms of the normal processing times of jobs for the total completion time minimization problem and the makespan minimization problem.     

Behavioral optimal insurance

The present work studies the optimal insurance policy offered by an insurer adopting a proportional premium principle to an insured whose decision-making behavior is modeled by Kahneman and Tversky’s Cumulative Prospect Theory with convex probability distortions. We show that, under a fixed premium rate, the optimal insurance policy is a generalized insurance layer (that is, either an insurance layer or a stop–loss insurance). This optimal insurance decision problem is resolved by first converting it into three different sub-problems similar to those in Jin and Zhou (2008); however, as we now demand a more regular optimal solution, a completely different approach has been developed to tackle them. When the premium is regarded as a decision variable and there is no risk loading, the optimal indemnity schedule in this form has no deductibles but a cap; further results also suggests that the deductible amount will be reduced if the risk loading is decreased. As a whole, our paper provides a theoretical explanation for the popularity of limited coverage insurance policies in the market as observed by many socio-economists, which serves as a mathematical bridge between behavioral finance and actuarial science.     

Optimal appointment scheduling in continuous time: The lag order approximation method

We study appointment scheduling problems in continuous time. A finite number of clients are scheduled such that a function of the waiting time of clients, the idle time of the server, and the lateness of the schedule is minimized. The optimal schedule is notoriously hard to derive within reasonable computation times. Therefore, we develop the lag order approximation method, that sets the client’s optimal appointment time based on only a part of his predecessors. We show that a lag order of two, i.e., taking two predecessors into account, results in nearly optimal schedules within reasonable computation times. We illustrate our approximation method with an appointment scheduling problem in a CT-scan area.     

Behavioral optimal insurance

The present work studies the optimal insurance policy offered by an insurer adopting a proportional premium principle to an insured whose decision-making behavior is modeled by Kahneman and Tversky’s Cumulative Prospect Theory with convex probability distortions. We show that, under a fixed premium rate, the optimal insurance policy is a generalized insurance layer (that is, either an insurance layer or a stop–loss insurance). This optimal insurance decision problem is resolved by first converting it into three different sub-problems similar to those in Jin and Zhou (2008); however, as we now demand a more regular optimal solution, a completely different approach has been developed to tackle them. When the premium is regarded as a decision variable and there is no risk loading, the optimal indemnity schedule in this form has no deductibles but a cap; further results also suggests that the deductible amount will be reduced if the risk loading is decreased. As a whole, our paper provides a theoretical explanation for the popularity of limited coverage insurance policies in the market as observed by many socio-economists, which serves as a mathematical bridge between behavioral finance and actuarial science.     

不确定性对混合CVaR约束库存系统的影响

运用应用概率中的随机占优研究需求不确定性对混合CVaR约束库存系统最优订购量和最优利润的影响。引入刻画决策者风险态度的“风险偏好系数”,得到系统最优订购量和最优利润关于风险偏好系数的单调性。研究表明随机大需求总会导致系统较高的最优订购量和最优利润;在割准则序意义下,最优订购量可能随需求可变性的增加而增加也可能随需求可变性的增加而减少;在二阶随机占优且风险偏好系数大于等于1的情况下系统最优利润具有随机单调性,然而当风险偏好系数小于1时最优利润在二阶随机占优意义下的结论不一定成立,我们通过一个数值例子来说明。     

Minimizing total flow time in the single-machine scheduling problem with periodic maintenance

This paper deals with a single-machine scheduling problem with limited machine availability. The limited availability of machine results from periodic maintenance activities. In our research, a periodic maintenance schedule consists of several maintenance periods. Each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the total flow time subject to periodic maintenance and nonresumable jobs. Some important theorems are proved for the problem. A branch-and-bound algorithm that utilizes several theorems is proposed to find the optimal schedule. We also develop a heuristic to solve large sized problems. In this paper, computational results show that the proposed heuristic is highly accurate and efficient.     

A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect

This paper considers a scheduling model involving two agents, job release times, and the sum-of-processing-times-based learning effect. The sum-of-processing-times-based learning effect means that the actual processing time of a job of either agent is a decreasing function of the sum of the processing times of the jobs already scheduled in a given schedule. The goal is to seek for an optimal schedule that minimizes the total weighted completion time of the first agent, subject to no tardy job for the second agent. We first provide a branch-and-bound method to solve the problem. We then develop an approach that combines genetic algorithm and simulated annealing to seek for approximate solutions for the problem. We carry on extensive computational tests to assess the performance of the proposed algorithms.     

Coordination mechanisms for parallel machine scheduling

We consider coordination mechanisms for the distributed scheduling of n jobs on m parallel machines, where each agent holding a job selects a machine to process his/her own job. Without a central authority to construct a schedule, each agent acts selfishly to minimize his/her own disutility, which is either the completion time of the job or the congestion time (defined as the load of the machine on which the job is scheduled). However, the overall system performance is measured by a central objective which is quite different from the agents’ objective. In the literature, makespan is often considered as the central objective. We, however, investigate problems with other central objectives that minimize the total congestion time, the total completion time, the maximum tardiness, the total tardiness, and the number of tardy jobs. The performance deterioration of the central objective by a lack of central coordination, referred to as the price of anarchy, is typically measured by the maximum ratio of the objective function value of a Nash equilibrium schedule versus that of an optimal, coordinated schedule. In this paper we give bounds for the price of anarchy for the above objectives. For problems with due date related objectives, the price of anarchy may not be defined since the optimal value may be zero. In this case, we consider the maximum difference between the objective function value of an equilibrium schedule and the optimal value. We refer to this metric as the absolute price of anarchy and analyze its lower and upper bounds.     

A hybrid heuristic and linear programming approach to multi-product machine scheduling

A new heuristic approach is presented for scheduling economic lots in a multi-product single-machine environment. Given a pre-defined master sequence of product setups, an integer linear programming formulation is developed which finds an optimal subsequence and optimal economic lots. The model takes explicit account of initial inventories, setup times and allows setups to be scheduled at arbitrary epochs in continuous time, rather than restricting setups to a discrete time grid. We approximate the objective function of the model and solve to obtain an optimal capacity feasible schedule for the approximate objective. The approach was tested on a set of randomly generated problems, generating solutions that are on average 2.5% above a lower bound on the optimal cost. We also extend the approach to allow shortages.     

从管理风险的角度看金融风险度量

本文得出了连续时间下均值-VaR模型的最优投资策略。在这个最优解的基础上,我们比较说明了概率和分位数作为风险度量方法在管理风险中发挥的作用。我们的分析结果表明:从管理风险的角度出发控制损失发生的概率要比控制损失的水平更为有意义;并且选择的VaR置信度水平越高,监管的效果会越好。     

基于改进混合遗传算法安排生产调度

研究了某工厂生产调度问题,建立了数学模型.针对这一实际问题,通过引入小生境技术、最优保存策略、近优淘汰策略、自适应调整交叉概率和变异概率,设计了用于求解多个最优顺序的混合遗传算法,用所设计的混合遗传算法对该模型进行了计算,获得了许多最优顺序,这就使得生产调度安排灵活机动,便于智能调度,同时生产量比原来大幅度提高.这表明使用混合遗传算法安排生产调度是非常有效的.     

Scheduling workforce relief breaks in advance versus in real-time

This paper focuses upon employee rest breaks, or reliefs, in workforce scheduling. Historically, the workforce scheduling literature has largely ignored reliefs, as less than 18% of the 64 papers we surveyed scheduled reliefs. The argument has been that one need not schedule reliefs in advance, since they can easily be scheduled in real-time. We find this argument to be flawed. We show that failing to schedule reliefs in advance will have one of two undesirable outcomes. First, there will be a less profitable deployment of labor should all reliefs actually be taken in real-time. Second, if some reliefs are never assigned or if relief-timing restrictions are relaxed so that more reliefs may be assigned in real-time, there will be a disgruntled and less productive workforce and perhaps violations of contractual obligations. Our findings are supported by anecdotal evidence drawn from commercial labor scheduling software.     

Single-machine scheduling of proportionally deteriorating jobs by two agents

We consider a problem of scheduling a set of independent jobs by two agents on a single machine. Every agent has its own subset of jobs to be scheduled and uses its own optimality criterion. The processing time of each job proportionally deteriorates with respect to the starting time of the job. The problem is to find a schedule that minimizes the total tardiness of the first agent, provided that no tardy job is allowed for the second agent. We prove basic properties of the problem and give a lower bound on the optimal value of the total tardiness criterion. On the basis of these results, we propose a branch-and-bound algorithm and an evolutionary algorithm for the problem. Computational experiments show that the exact algorithm solves instances up to 50 jobs in a reasonably short time and that solutions obtained by the metaheuristic are close to optimal ones.     

Scheduling open shops with parallel machines

The parallel shop and the open shop are two machine environments that have received much attention in the literature of scheduling theory. A common generalization—the open shop with parallel machines—is considered in this paper. Polynomial-time algorithms are presented for obtaining minimum-length preemptive schedules for three cases. Open shops with single-operation machines of equal speed are scheduled with essentially no more difficulty than an ordinary open shop. Open shops with multiple-operation machines of equal speed are scheduled with the aid of a sequence of network flow computations. The general open shop problem with parallel machines of arbitrary speeds can be solved by linear programming, in much the same way as an optimal preemptive schedule can be found for unrelated parallel machines.