Scheduling spatially distributed jobs with degradation: Application to pothole repair

This paper considers scheduling spatially distributed jobs with degradation. A mixed integer programming (MIP) model is developed for the linear degradation case in which no new jobs arrive. Properties of the model are analyzed, following which three heuristics are developed, enhanced greedy, chronological decomposition and simulated annealing. Numerical tests are conducted to: (i) establish limits of the exact MIP solution, (ii) identify the best heuristic based on an analysis of performance on small problem instances for which exact solutions are known, (iii) solve large problem instances and obtain lower bounds to establish solution quality, and (iv) study the effect of three key model parameters. Findings from our computational experiments indicate that: (i) exact solutions are limited to instances with less than 14 jobs; (ii) the enhanced greedy heuristic followed by the application of the simulated annealing heuristic yields high quality solutions for large problem instances in reasonable computation time; and (iii) the factors “degradation rate” and “work hours” have a significant effect on the objective function. To demonstrate applicability of the model, a case study is presented based on a pothole repair scenario from Buffalo, New York, USA. Findings from the case study indicate that scheduling spatially dispersed jobs with degradation such as potholes requires: (i) careful consideration of the number of servers assigned, degradation rate and depot location; (ii) appropriate modeling of continuously arriving jobs; and (iii) appropriate incorporation of equity consideration.     

Scheduling identical jobs on uniform parallel machines

We address the problem of scheduling n identical jobs on m uniform parallel machines to optimize scheduling criteria that are nondecreasing in the job completion times. It is well known that this can be formulated as a linear assignment problem, and subsequently solved in O ( n ³) time. We give a more concise formulation for minsum criteria, and show that general minmax criteria can be minimized in O ( n ²) time. We present faster algorithms, requiring only O ( n + m log m ) time for minimizing makespan and total completion time, O ( n log n ) time for minimizing total weighted completion time, maximum lateness, total tardiness and the weighted number of tardy jobs, and O ( n log² n ) time for maximum weighted tardiness. In the case of release dates, we propose an O ( n log n ) algorithm for minimizing makespan, and an O ( mn ^2m+1) time dynamic programming algorithm for minimizing total completion time.     

配送中心车辆调度模型及遗传算法设计

针对物流配送中心车辆调度问题,采用混合整数规划方法进行建模。对实际问题进行研兖分析后,基于所研究问题的特点,提出基于遗传算法的求解方法。通过数值实验对算法不同参数组合进行分析、比较,获得最佳参数组合．建立了有效的求解该问题的遗传算法。并通过对实际问题的数值仿真试验．验证了算法的有效性。     

一种分布式呼叫中心排班模型

人员排班问题是呼叫中心运作的关键问题,因为呼叫中心60％-70％的成本是人员成本.近年来,分布式呼叫中心的出现给排班的建模与求解带来了新的挑战.基于对分布式呼叫中心排班的理解,论文提出了公平排班的原则,并提出了基于公平原则的混合整数排班模型,通过算例实验证明,排班模型能够较好地平衡多个呼叫中心分中心的工作量,并能在较短的时间内获得满意解.     

Decomposition of the Koopmans-Beckmann Problem

Subsequent findings indicate that the Koopmans-Beckmann linear programming representation of the quadratic assignment problem may be more useful in solving for the best integer assignment and a set of sustaining prices than their initial results suggest. In response to the renewed interest in the quadratic assignment problem, this brief paper presents the Koopmans-Beckmann linear program in general matrix form, demostrates that the program is decomposable, and shows that the primal subprogram constitutes a simple linear assignment problem whose optimal solution set always contains at least one integer assignment of plants to locations.     

Optimal locations and flow allocations for aggregation hubs in supply chain networks of perishable products

Establishment of aggregation hubs in a supply chain network (SCN) is typically a facility location-allocation (FLA) decision, which is known to be a NP-hard optimization problem. Considering the flow of heterogeneous perishable products, like fresh produce, with different spoilage rates, further increases the complexity of such a problem. This is due to the effect of transportation time and conditions, services provided in the hub, and hub proximity to supply sources, on the quality and quantity of products eventually reaching the demand destinations, and hence on the location-allocation decision. In this paper, this problem is formulated as a mixed integer linear programming (MILP) model that considers a number of problem characteristics simultaneously for the first time, to minimize the transportation, spoilage, processing, and capacity-based hub establishment costs. Due to its complexity, two hybrid algorithms that combine a meta-heuristic with a perishability-modified transportation algorithm, are proposed to solve the problem. The algorithms are based on binary particle swarm optimization (BPSO) and simulated annealing (SA). Taguchi analysis is used to tune the significant parameters of both algorithms considering different problem sizes. Computational analysis is further conducted to evaluate and compare the performances of the algorithms using randomly generated test instances and exact solutions obtained using CPLEX. Results show that while both algorithms are capable of obtaining optimum solutions for most instances, the hybrid BPSO slightly outperforms the hybrid SA in terms of consistency and solution time.     

Supplier evaluation and demand allocation among suppliers in a supply chain

This paper presents a hybrid algorithm that prioritizes the suppliers and then allocates the demand among the suppliers. The objective here is to maximize the total purchase value of the items taking into consideration budget constraint, demand condition, delivery lead-time and supplier capacity. Since the problem is multi-criteria decision making, we solve this problem by integrating the supplier rating with mixed linear integer programming method. The customer demand is allocated by using a hybrid algorithm based on the technique for order preference by similarity to ideal solution (TOPSIS) and the mixed linear integer programming (MILP) approaches. The effectiveness of the proposed algorithm is validated with computational results. Drawing to a case, a supplier S₃ is identified as the best supplier by using the TOPSIS method for demand allocation under no restrictions. On the contrary, under constrained scenario, supplier S₂ is selected as the best supplier by using the hybrid algorithm for demand allocation and maximum units are allocated to S₂.     

Two heuristics for the deterministic,single operator,multiple machine,multiple run cyclic scheduling problem

The semiautomatic nature of machinery often makes it economical to assign more than one machine to a single operator. Multi-machine assignments are common in the textile, tooling and molding industries. They are also found where numerically controlled (NC) machinery are used and, more recently, where flexible manufacturing systems (FMS) are employed. Previous work on deterministic cyclic scheduling models has focused on determining the optimal number of usually identical machines with single runs to assign to an operator. In practice, the schedules are represented by man/machine charts.When, due to production requirements, we mix different types of runs with known times on non-identical machines, we have the deterministic, single operator, multiple machine, multiple run, cyclic scheduling problem. We present two heuristics for solving this more realistic generalization of earlier problems. For the nonidentical, multiple run case, the scheduling of the runs is crucial in minimizing the cycle time of the system. The integer programming formulation of small problems is large, and solving it directly could require excessive computation time on a large mainframe computer.Heuristic 1 selects the next machine run to schedule by minimizing the total immediate waiting cost of the operator and machines. The hourly machine costs reflect the relative merit of utilizing certain machines over others. Heuristic 2 first schedules the machine with the longest automatic processing time of run one. It then follows Heuristic 1 until the long processing time of the first run has ended. The next available run with the longest automatic processing time is then scheduled, and the process repeats. The underlying notion is that many short runs may be performed during the long automatic run of a machine.The heuristics are polynomially bounded, can be easily implemented on a mini- or micro-computer and in practice should be much faster than integer programming methods. In addition to the heuristics, we compute a lower bound on the cycle time. We use this bound as a measure of the effectiveness of a solution. If for a given schedule, the cycle time equals its lower bound, then the solution is optimal.Both heuristics were coded in FORTRAN on a CDC-6600 computer. An interactive version was also developed for a DEC PDP11/70. A detailed computational study is presented. In it, both heuristics solved 50 machine, 5 run problems in less than 10 CPU seconds on the CDC-6600. Computational experience indicates that the heuristics are efficient and often find schedules which have cycle times within 10% the lower bound.     

A statistical screening procedure for goal programming algorithm selection

Many of the linear goal programming algorithms that are available today are based on a simplex type solution method that begins with an initial simplex tableau whose solution set variables (i.e. basic variables) consist of all negative deviational variables or all positive deviational variables. Prior research has shown that computational solution effort can be reduced if the appropriate all negative or all positive deviational variable algorithm is selected. This paper presents a practical statistical screening procedure that can be used in conjunction with previously published selection criteria to reduce computational effort by selecting the appropriate algorithm for all types of applied goal programming models. Results of the study reveal the accuracy of the statistical screening procedure when it is applied to a large sample of goal programming problems.     

The Loading Optimization: A Novel Integer Linear Programming Model

ABSTRACT

This paper establishes a new integer linear programming model for container loading problem. This model can be used to calculate the optimal loading plan for each container. To solve the model, in this paper, the model problem is decomposed into two easy to solve sub-problems: auxiliary problem (AP) and transportation problem, and prove by solving the two sub-problems can quickly and efficiently to find the optimal solution of the model. Finally, an example is given to illustrate the solution process, which shows that the algorithm can give the optimal stowage scheme quickly and effectively.     

Tight LP-based lower bounds for wavelength conversion in optical networks

With the introduction of optical switching technology in telecommunication networks, all-optical connections, so-called lightpaths, can be established. Lightpaths have to be assigned a wavelength in such a way that no two lightpaths sharing a fiber use the same wavelength. The wavelength of operation can only be exchanged by the deployment of a wavelength converter. In this paper, we study the minimum converter wavelength assignment problem. We develop three integer programming formulations to minimize the number of converters and study their properties. Where the first two formulations lack the power to provide non-trivial lower bounds, tight lower bounds can be computed by solving the linear relaxation of the third formulation by delayed column generation. In fact, the lower bound equals the best known solution value for all realistic instances at our disposal. In a computational study, we compare different strategies to enhance the column generation algorithm.     

石油海运领域运筹优化方法应用研究综述

为研究运筹方法在石油海运领域的应用及前景,检索1980年至今的国内外相关文献,系统归纳提出石油海上运输优化问题的场景分类:海上运输优化、在港作业调度优化以及油船驳运,分析并对比了各研究的模型差异及算法优劣,最后提出了全局优化调度、根据实际添加特殊约束和设置变量、利用规划约束及人工智能等方式弥补线性规划求解的不足等研究建议。     

A volume and material handling cost based heuristic for designing cellular manufacturing cells

One of the major problems in a group technology or cellular manufacturing environment is the formation of part groups and machine cells. Because of the combinatorial nature of the cell formation problem, it is difficult to solve the problem optimally. Most of the procedures related to cell design in cellular manufacturing operate on the part-machine incidence matrix in an attempt to identify block diagonality. If complete block diagonality does not exist, the decision about cell configuration is left to the subjective judgement of the designer. These procedures are also generally based on part routing only, and do not consider part volume and material handling costs.In this paper we develop an integer programming model, as well as a heuristic to effectively assign machines to cells. In these procedures we consider component volumes, costs related to movement of components between and within cells, and penalty for not using all machines in a cell visited by a component. Since the integer programming formulation becomes large even for small problems, an efficient heuristic is developed to solve larger problems. The heuristic solutions to 180 randomly generated small problems were compared against the optimal solutions obtained by the integer programming model. The heuristic has been found to identify optimal solutions in all 180 cases.This heuristic is also compared to several well known algorithms on 900 larger test problems. These problems were generated to cover a wide range of environmental situations such as varying levels of block diagonality in the part-machine incidence matrix, and diversity in the component volumes and material handling costs. In 99% of the problems our heuristic generated solutions which are better or as good as the best solution obtained by other algorithms. Further, in situations where complete block diagonality in the part-machine incidence matrix did not exist, our heuristic produced even better results. Since the maximum number of iterations required in our heuristic is the number of machines in the problem, the heuristic is computationally efficient.     

A university admissions system

This paper presents a mathematical programming model that will make admit/reject decisions for applicants to a university freshman class.The model is intended to aid (rather than replace) reviewers and will help produce better and more consistent decisions. It also provides a university administration with some control over “balance” in the composition of the student body and allows investigation of the consequences of alternative admission policies.The nature of the problem suggests an integer programming formulation, however it is shown that a linear programming formulation will provide an efficient and practical solution for all but a very small set of applicants (no more than 19).     

The complexity of linear programming

The simplex method for linear programming has always been very successful from a practical point of view. In the worst case, however, the method may require a computational effort that increases exponentially with problem size. Recently L.G. K hachian proposed an entirely different solution method whose running time is bounded by a polynomial function of problem size, thereby settling a major open problem in computational complexity theory. We review the developments preceding K hachian 's discovery, describe the algorithm and discuss its implications.     

数学规划在测绘工作中的应用

本文在介绍数学规划的相关方法包括线性规划、灵敏度分析、整数规划的基础上,从一个例子出发,讨论了在测绘生产工作中,在不同的条件下,数学规划方法的应用。     

具有模糊加工时间的偏柔性作业车间调度问题研究

研究了以最小化制造跨度为目标的,具有模糊加工时间的偏柔性作业车间调度问题。针对该问题,采用三角模糊数来表征时间参数;并采用预处理算法,将偏柔性作业车间调度问题转化为更容易处理的完全柔性作业车间调度问题,给出了基于粒子群优化的调度模型;最后通过实例验证了模型的有效性。     

Solving the generalized transportation problem

This paper advocates a mathematical programming approach for solving the classical transportation problem generalized to include non-linear demand and supply functions and non-linear transport costs. Such an approach is made possible by the recent public availability of a powerful optimizing system called MINOS, assembled for the solution of large programming problems for which the constraint set is linear and spatial. Primal and dual program formulations for this generalized transportation problem are set out in the paper, and brief computational experience with the software system in solving several illustrative problems is recorded.