呼叫中心坐席人员排班问题优化模型与算法研究

国内呼叫企业在保证每个坐席人员周内当值相同班次情况下,通过灵活安排周内当班日期与班次来制定排班方案。针对该实际排班场景,构建问题整数规划模型。通过对问题数据特征及优化性质分析,以及对班次人力有效满足区段电话服务需求的量化指标表征,分别提出两个构造性启发式算法。使用企业实例数据对模型算法进行计算实验。实验结果显示,整数规划模型适合于求解小规模排班问题最优解,而启发式算法能够以小计算成本获得大规模排班问题优化解。最后讨论保证员工上班规律性的同班次用工制度对企业人力成本控制的影响。     

Solving a multicoloring problem with overlaps using integer programming

This paper presents a new generalization of the graph multicoloring problem. We propose a Branch-and-Cut algorithm based on a new integer programming formulation. The cuts used are valid inequalities that we could identify to the polytope associated with the model. The Branch-and-Cut system includes separation heuristics for the valid inequalities, specific initial and primal heuristics, branching and pruning rules. We report on computational experience with random instances.     

General Purpose Heuristics for Integer Programming—Part II

In spite of the many special purpose heuristics for specific classes of integer programming (IP) problems, there are few developments that focus on general purpose integer programming heuristics. This stems partly from the perception that general purpose methods are likely to be less effective than specialized procedures for specific problems, and partly from the perception that there is no unifying theoretical basis for creating general purpose heuristics. Still, there is a general acknowledgment that methods which are not limited to solving IP problems on a class by class basis, but which apply to a broader range of problems, have significant value. We provide a theoretical framework and associated explicit proposals for generating general purpose IP heuristics. Our development, makes use of cutting plane derivations that also give a natural basis for marrying heuristics with exact branch and cut methods for integer programming problems.     

General purpose heuristics for integer programming—Part I

In spite of the many special purpose heuristics for specific classes of integer programming (IP) problems, there are few developments that focus on general purpose integer programming heuristics. This stems partly from the perception that general purpose methods are likely to be less effective than specialized procedures for specific problems, and partly from the perception that there is no unifying theoretical basis for creating general purpose heuristics. Still, there is a general acknowledgment that methods which are not limited to solving IP problems on a class by class basis, but which apply to a broader range of problems, have significant value. We show that certain ideas proposed in the 1970s, which are often overlooked, can be reformulated and linked with more recent developments to give a useful theoretical framework for generating general purpose IP heuristics. This framework, which has the appeal of being highly visual, makes use of cutting plane derivations that also give a natural basis for marrying heuristics with exact branch and cut methods for integer programming problems.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

Lagrangian heuristics for scheduling new product development projects in the pharmaceutical industry

To stay ahead of their competition, pharmaceutical firms must make effective use of their new product development (NPD) capabilities by efficiently allocating its analytical, clinical testing and manufacturing resources across various drug development projects. The resulting project scheduling problems involve coordinating hundreds of testing and manufacturing activities over a period of several quarters. Most conventional integer programming approaches are computationally impractical for problems of this size, while priority rule-driven heuristics seldom provide consistent solution quality. We propose a Lagrangian decomposition (LD) heuristic that exploits the special structure of these problems. Some resources (typically manpower) are shared across all on-going projects while others (typically equipment) are specific to individual project categories. Our objective function is a weighted discounted cost expressed in terms of activity completion times. The LD heuristics were subjected to a comprehensive experimental study based on typical operational instances. While the conventional “Reward–Risk” priority rule heuristic generates duality gaps between 47–58%, the best LD heuristic achieves duality gaps between 10–20%. The LD heuristics also yield makespan reductions of over 30% over the Reward–Risk priority rule.     

Heuristics for convex mixed integer nonlinear programs

In this paper, we describe the implementation of some heuristics for convex mixed integer nonlinear programs. The work focuses on three families of heuristics that have been successfully used for mixed integer linear programs: diving heuristics, the Feasibility Pump, and Relaxation Induced Neighborhood Search (RINS). We show how these heuristics can be adapted in the context of mixed integer nonlinear programming. We present results from computational experiments on a set of instances that show how the heuristics implemented help finding feasible solutions faster than the traditional branch-and-bound algorithm and how they help in reducing the total solution time of the branch-and-bound algorithm.     

A single-machine scheduling problem with maintenance activities to minimize makespan

We study a single-machine scheduling problem with periodic maintenance activity under two maintenance stratagems. Although the scheduling problem with single or periodic maintenance and nonresumable jobs has been well studied, most of past studies considered only one maintenance stratagem. This research deals with a single-machine scheduling problem where the machine should be stopped for maintenance after a fixed periodic interval (T) or after a fixed number of jobs (K) have been processed. The objective is to minimize the makespan for the addressed problem. A two-stage binary integer programming (BIP) model is provided for driving the optimal solution up to 350-job instances. For the large-sized problems, two efficient heuristics are provided for the different combinations of T and K. Computational results show that the proposed algorithm Best-Fit-Butterfly (BBF) performs well because the total average percentage error is below 1%. Once the constraint of the maximum number of jobs (K) processed in the machine’s available time interval (T) is equal or larger than half of jobs, the heuristic Best-Fit-Decreasing (DBF) is strongly recommended.     

A new Lagrangean approach to the pooling problem

We present a new Lagrangean approach for the pooling problem. The relaxation targets all nonlinear constraints, and results in a Lagrangean subproblem with a nonlinear objective function and linear constraints, that is reformulated as a linear mixed integer program. Besides being used to generate lower bounds, the subproblem solutions are exploited within Lagrangean heuristics to find feasible solutions. Valid cuts, derived from bilinear terms, are added to the subproblem to strengthen the Lagrangean bound and improve the quality of feasible solutions. The procedure is tested on a benchmark set of fifteen problems from the literature. The proposed bounds are found to outperform or equal earlier bounds from the literature on 14 out of 15 tested problems. Similarly, the Lagrangean heuristics outperform the VNS and MALT heuristics on 4 instances. Furthermore, the Lagrangean lower bound is equal to the global optimum for nine problems, and on average is 2.1% from the optimum. The Lagrangean heuristics, on the other hand, find the global solution for ten problems and on average are 0.043% from the optimum.     

A mixed integer linear programming formulation of the maximum betweenness problem

This paper considers the maximum betweenness problem. A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on randomly generated instances from the literature. The results of CPLEX solver, based on the proposed MILP formulation, are compared with results obtained by total enumeration technique. The results show that CPLEX optimally solves instances of up to 30 elements and 60 triples in a short period of time.     

Scheduling multiple orders per job in a single machine to minimize total completion time

This paper deals with a single-machine scheduling problem with multiple orders per job (MOJ) considerations. Both lot processing machines and item processing machines are also examined. There are two primary decisions that must be made in the proposed problem: (1) how to group the orders together, and (2) how to schedule the jobs once they are formed. In order to obtain the optimal solution to a scheduling problem, these two decisions should be made simultaneously. The performance measure is the total completion time of all orders. Two mixed binary integer programming models are developed to optimally solve this problem. Also, two efficient heuristics are proposed for solving large-sized problems. Computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics.     

Multiobjective GRASP with Path Relinking

In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report on empirical tests with 70 instances and 30 algorithms, that show that the proposed heuristics are competitive with the state-of-the-art methods for these problems.     

Strategies for designing energy-efficient clusters-based WSN topologies

Wireless Sensor Networks are used in several practical applications such as environmental monitoring and risk detection. In this work, we deal with the problem of organizing the network topology into clusters in order to minimize the total energy consumption. The problem is modeled as an Independent Dominating Problem with Connecting requirements. We first present a state-of-the-art on the problems to optimize energy consumption in WSN. Then, we propose a mixed integer linear programming formulation, constructive heuristics, a local search procedure, and a GRASP-based metaheuristic. Results are provided for large scale WSN instances.     

Heuristics for the multi-level capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) problem is fundamental to the design of centralized communication networks. In this paper we consider the multi-level capacitated minimum spanning tree problem, a generalization of the well-known CMST problem. Based on work previously done in the field, three heuristics are presented, addressing unit and non-unit demand cases. The proposed heuristics have been also integrated into a mixed integer programming solver. Evaluation results are presented, for an extensive set of experiments, indicating the improvements that the heuristics bring to the particular problem.     

Heuristics Ancient and Modern: Transport Scheduling Through the Ages

Heuristics which have been developed for transport scheduling over a lengthy period starting in 1960 are presented. They are generated in response to requirements to solve practical problems, and most are now in regular use by bus and train companies. Mathematical programming models have been formulated for some of the problems, but have been inappropriate on their own; in some cases, heuristics have led to a reduced problem which has then been solved by integer linear programming. The paper is designed to illustrate the development of heuristics for a range of related problem areas over nearly forty years. It explores the relationships between heuristics and other approaches and emphasises the need to convince users of the suitability of the overall system. Where appropriate, indications are given of difficulties in achieving practical implementation.     

Revisiting dynamic programming for finding optimal subtrees in trees

In this paper we revisit an existing dynamic programming algorithm for finding optimal subtrees in edge weighted trees. This algorithm was sketched by Maffioli in a technical report in 1991. First, we adapt this algorithm for the application to trees that can have both node and edge weights. Second, we extend the algorithm such that it does not only deliver the values of optimal trees, but also the trees themselves. Finally, we use our extended algorithm for developing heuristics for the k-cardinality tree problem in undirected graphs G with node and edge weights. This NP-hard problem consists of finding in the given graph a tree with exactly k edges such that the sum of the node and the edge weights is minimal. In order to show the usefulness of our heuristics we conduct an extensive computational analysis that concerns most of the existing problem instances. Our results show that with growing problem size the proposed heuristics reach the performance of state-of-the-art metaheuristics. Therefore, this study can be seen as a cautious note on the scaling of metaheuristics.     

A New Formulation for Spanning Trees

Spanning trees are fundamental structures in graph theory. Furthermore, computing them is a central part in many relevant algorithms, used in either practical or theoretical applications. The classical Minimum Spanning Tree problem is solvable in polynomial time but almost all of its variants are NP-Hard. In this paper, a novel polynomial size mixed integer linear programming formulation is introduced for spanning trees. This formulation is based on a new characterization we propose for acyclic graphs. Preliminary computational results show that this formulation is capable of solving small instances of the diameter constrained minimum spanning tree problem. It should be possible to strengthen the formulation to tackle larger instances of that problem. Additionally, our spanning tree formulation may prove to be a more effective model for some related applications.     

物流服务供应链订单分配优化及其遗传算法

针对物流服务供应链订单分配问题中,物流服务集成商通常会按照所分配的订单价值向分包商收取一定比例交易费用的特点,设定交易费用为交易额的线性函数,构建了新的物流服务供应链订单分配优化混合整数规划模型,其优化目标为最小化交易费用、采购费用、短缺服务与延迟供给的物流能力数量。鉴于问题的NP-hard特性,设计了相应的遗传算法,并结合基于优先权的启发式规则避免了大量非法初始解的出现。实验算例表明所建立的模型能够反映物流服务供应链订单分配过程中的线性交易费用因素,其所设计的算法能够在可接受的时间内获得质量较高的满意解,并且对于大规模订单分配优化问题,遗传算法的求解时间与求解结果要优于LINGO软件。     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

Order and static stability into the strip packing problem

This paper investigates the two-dimensional strip packing problem considering the case in which items should be arranged to form a physically stable packing satisfying a predefined item unloading order from the top of the strip. The packing stability analysis is based on conditions for the static equilibrium of rigid bodies, differing from others strategies which are based on area and percentage of support. We consider an integer linear programming model for the strip packing problem with the order constraint, and a cutting plane algorithm to handle stability, leading to a branch-and-cut approach. We also present two heuristics: the first is based on a stack building algorithm; and, the last is a slight modification of the branch-and-cut approach. The computational experiments show that the branch-and-cut model can handle small and medium-sized instances, whereas the heuristics found almost optimal solutions quickly for several instances. With the combination of heuristics and the branch-and-cut algorithm, many instances are solved to near optimality in a few seconds.