Heuristic solutions to the long-term unit commitment problem with cogeneration plants

We consider a long-term version of the unit commitment problem that spans over one year divided into hourly time intervals. It includes constraints on electricity and heating production as well as on biomass consumption. The problem is of interest for scenario analysis in long-term strategic planning. We model the problem as a large mixed integer programming problem. Two solutions to this problem are of interest but computationally intractable: the optimal solution and the solution derived by market simulation. To achieve good and fast approximations to these two solutions, we design heuristic algorithms, including mixed integer programming heuristics, construction heuristics and local search procedures. Two setups are the best: a relax and fix mixed integer programming approach with an objective function reformulation and a combination of a dispatching heuristic with stochastic local search. The work is developed in the context of the Danish electricity market and the computational analysis is carried out on real-life data.     

Optimizing disassembly processes subjected to sequence-dependent cost

Detection of the optimum disassembly sequence for a given product can proceed via mathematical programming, which is based on the AND/OR graph representation of its disassembly process. This is called the exact method for it reveals the global optimum. This paper describes an extension of the exact method in case sequence-dependent costs are considered. Previously presented methods confined themselves either to sequential disassembly, or were based on heuristics. The only exact method for the full problem known so far, needs an elaborate transformation of the AND/OR graph, and is based on integer linear programming. This paper discusses an alternate approach that uses a binary integer linear programming approach and that lacks the need of transforming the AND/OR graph. The proposed method is applied to arbitrary instances of some product structures that have been taken from the literature. Apart from this, the method is applied to an expandable AND/OR graph, that enables gradual increase of product complexity. It is demonstrated that the convergence of the iteration process is satisfactory, and the required CPU time appears comparatively small and only moderately increases with the number of constraints. It appears that the method applies to products with a complexity that cannot be managed with the integer linear programming model. The iterative method is promising for dealing with modularized products and as a benchmark for heuristic algorithms, which are used if products exhibit still higher complexity.     

Binary integer programming formulation and heuristics for differentiated coverage in heterogeneous sensor networks

Coverage is a fundamental task in sensor networks. We consider the minimum cost point coverage problem and formulate a binary integer linear programming model for effective sensor placement on a grid-structured sensor field when there are multiple types of sensors with varying sensing quality and price. The formulation is general and can be adapted to handle situations where sensing is perfect, imperfect or uncertain, and the coverage requirements are differentiated. Unfortunately, the new model suffers from the intractability of the binary integer programming formulations. We therefore suggest approximation algorithms and heuristics. Computational results indicate that the heuristic based on Lagrangean relaxation outperforms the others in terms of solution quality.     

Coordinated scheduling of production and delivery from multiple plants

This paper deals with the scheduling of orders and vehicle assignment for production and distribution planning in a scenario of no-wait, immediate delivery to the customer site. We first describe the problem and then present an integer programming model that maximizes the weighted value of the orders served. We consider a special case of the problem which can be solved in polinomial time by a minimum cost flow algorithm. Based on this approach we develop a heuristic procedure for the general case. Comparisons with an exact graph-based method attest that our heuristic produces good-quality solutions in short running times.     

Recursive central rounding for mixed integer programs

We introduce a new rounding heuristic for mixed integer programs. Starting from a fractional solution, the new approach is based on recursively fixing a subset of the discrete variables while using the analytic center to re-center the remaining ones. The proposed rounding approach can be used independently or integrated with other heuristics. We demonstrate both setups by first using the proposed approach to round the optimal solution of the linear programming relaxation. We then integrate the proposed rounding heuristic with the feasibility pump by replacing the original simple rounding function of the feasibility pump. We conduct computational testing on mixed integer problems from MIPLIB and CORAL and on mixed integer quadratic problems from MIQPLIB. The proposed algorithm is computationally efficient and provides good quality feasible solutions.     

A tabu search algorithm for order acceptance and scheduling

We consider a make-to-order production system, where limited production capacity and order delivery requirements necessitate selective acceptance of the orders. Since tardiness penalties cause loss of revenue, scheduling and order acceptance decisions must be taken jointly to maximize total revenue. We present a tabu search algorithm that solves the order acceptance and scheduling problem on a single machine with release dates and sequence dependent setup times. We analyze the performance of the tabu search algorithm on an extensive set of test instances with up to 100 orders and compare it with two heuristics from the literature. In the comparison, we report optimality gaps which are calculated with respect to bounds generated from a mixed integer programming formulation. The results show that the tabu search algorithm gives near optimal solutions that are significantly better compared to the solutions given by the two heuristics. Furthermore, the run time of the tabu search algorithm is very small, even for 100 orders. The success of the proposed heuristic largely depends on its capability to incorporate in its search acceptance and scheduling decisions simultaneously.     

单阶段多产品批处理过程的短期调度1. 基本模型的建立

具有并行设备的多产品单阶段批处理过程短期 调度问题需考虑订单发布时间、交货期，订单生产的顺序相关建立时间、禁止生产子序列， 及设备的准备时间等生产约束．本文在考虑上述约束的基础的上，利用时间间隙的概念和连 续时间表达，将设备、订单分配给时间间隙分别表达为两类0-1变量，建立了具有并行生产 线的多产品单阶段批处理过程的短期调度数学模型．模型表达为一个混合整数规划（MILP） 问题．该模型不但比已有的基于时间间隙描述的调度模型0-1变量少，而且能优 化多种目标函数．本文的第二部分将引入一些适当的启发性规则，减小了模型的规模，并应 用大量的计算实例说明该模型的有效性和适用性．     

Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics

We propose a general-purpose heuristic approach combining metaheuristics and mixed integer programming to find high quality solutions to the challenging single- and parallel-machine capacitated lotsizing and scheduling problem with sequence-dependent setup times and costs. Commercial solvers fail to solve even medium-sized instances of this NP-hard problem; therefore, heuristics are required to find competitive solutions. We develop construction, improvement and search heuristics all based on MIP formulations. We then compare the performance of these heuristics with those of two metaheuristics and other MIP-based heuristics that have been proposed in the literature, and to a state-of-the-art commercial solver. A comprehensive set of computational experiments shows the effectiveness and efficiency of the main approach, a stochastic MIP-based local search heuristic, in solving medium to large size problems. Our solution procedures are quite flexible and may easily be adapted to cope with model extensions or to address different optimization problems that arise in practice.     

Makespan minimization on single batch-processing machine via ant colony optimization

This paper investigates the problem of minimizing makespan on a single batch-processing machine, and the machine can process multiple jobs simultaneously. Each job is characterized by release time, processing time, and job size. We established a mixed integer programming model and proposed a valid lower bound for this problem. By introducing a definition of waste and idle space (WIS), this problem is proven to be equivalent to minimizing the WIS for the schedule. Since the problem is NP-hard, we proposed a heuristic and an ant colony optimization (ACO) algorithm based on the theorems presented. A candidate list strategy and a new method to construct heuristic information were introduced for the ACO approach to achieve a satisfactory solution in a reasonable computational time. Through extensive computational experiments, appropriate ACO parameter values were chosen and the effectiveness of the proposed algorithms was evaluated by solution quality and run time. The results showed that the ACO algorithm combined with the candidate list was more robust and consistently outperformed genetic algorithm (GA), CPLEX, and the other two heuristics, especially for large job instances.     

A heuristic for the vehicle routing problem with due times

This paper studies the vehicle routing problem with due times. The vehicles are supposed to visit customers within the due times, and a penalty cost is imposed in case the vehicle arrives past the due times. The objective is to minimize the weighted sum of the traveling time of vehicles and the tardiness of the service customers receive. A mixed integer programming formulation and a heuristic based on the tabu search for a practical use are suggested. Route-perturb and route-improvement method for the neighborhood generation is proposed. Performances are compared with other heuristics appeared in the literature using the bench-mark data set modified to be fit to the model. It is shown that the suggested heuristic gives a good solution in a short computation time.     

Hybrid approach for the two‐dimensional bin packing problem with two‐staged patterns

This paper presents a two‐phase heuristic approach for the two‐dimensional bin packing problem with two‐staged patterns and nonoriented items. A solution is generated in each phase and the better one is selected. Residual problems are solved by column generation in the first phase, where a partial admitting procedure is used to admit some of the patterns into the phase‐1 solution. The second solution is obtained from solving an integer linear programming problem over the set of all patterns generated in the first phase, where a time limit is used and subsequently the solution may not be optimal over the pattern set. The computational results indicate that the approach yields the best solution quality among the heuristics that use two‐staged or more complex patterns.     

Planning for Agricultural Forage Harvesters and Trucks: Model,Heuristics, and Case Study

In this paper we study an actual problem proposed by an agricultural cooperative devoted to harvesting corn and grass. The cooperative uses harvesters for harvesting the crop and trucks for carrying it from the smallholdings to the landowners’ silos. The goal is to minimize the total working time of the machinery. Therefore, the cooperative needs to plan both the harvesters and trucks routing. This routing problem simultaneously incorporates the following characteristics: time windows, nested decisions, processing times required to service each facility and the fact that facilities must be visited in clusters. A binary integer linear programming model is proposed to solve this problem. However, since approaches dealing directly with such formulation lead to considerable computation times, we propose a heuristic alternative solution approach for the problem. The heuristic is applied to the case of the cooperative “Os Irmandiños” with a large number of landowners and smallholdings. We report on extensive computational tests to show that the proposed heuristic approach can solve large problems effectively in reasonable computing time.     

Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties

The present paper studies the single machine, no-idle-time scheduling problem with a weighted quadratic earliness and tardiness objective. We investigate the relationship between this problem and the assignment problem, and we derive two lower bounds and several heuristic procedures based on this relationship. Furthermore, the applicability of the time-indexed integer programming formulation is investigated. The results of a computational experiment on a set of randomly generated instances show (1) the high-quality results of the proposed heuristics, (2) the low optimality gap of one of the proposed lower bounds and (3) the applicability of the integer programming formulation to small and medium size cases of the problem.     

基于混合元启发式算法的订单分批问题

订单拣选是仓库运营管理中一项高劳动强度与高成本的操作,拣货员在仓库中从货位拣选出满足订单需求的货物.订单分批问题(order batching problem, OBP)是订单拣选中的重要规划问题,该问题以最小化拣选批次路径时长为目标,将用户订单分配至拣选批次中.首先,为了优化订单分配构造高质量批次,提出一种混合元启发式算法,在自适应大邻域搜索框架中融入基于不可行下降的局部搜索,同时引入自适应惩罚机制和一批基于订单与基于批次的移除启发式以及新的算法组件;其次,为了优化拣选路径进一步降低批次旅行时间,提出单向启发式,利用动态规划优化组合多个路径策略.实验表明,在合理计算时间内,所提出算法的求解质量优于多重启变邻域搜索(MS-VNS)、混合自适应大邻域搜索及禁忌搜索(ALNS/TS),而且所提出算法的最大路径长度减少率达到22.36%.     

Mixed integer programming in production planning with backlogging and setup carryover: modeling and algorithms

This paper proposes a mixed integer programming formulation for modeling the capacitated multi-level lot sizing problem with both backlogging and setup carryover. Based on the model formulation, a progressive time-oriented decomposition heuristic framework is then proposed, where improvement and construction heuristics are effectively combined, therefore efficiently avoiding the weaknesses associated with the one-time decisions made by other classical time-oriented decomposition algorithms. Computational results show that the proposed optimization framework provides competitive solutions within a reasonable time.     

A quantum particle swarm optimization for the 0–1 generalized knapsack sharing problem

This study proposes a new hybrid heuristic approach that combines the quantum particle swarm optimization (QPSO) technique with a local search phase to solve the binary generalized knapsack sharing problem (GKSP). The approach also incorporates a heuristic repair operator that uses problem-specific knowledge instead of the penalty function technique commonly used for constrained problems. This study is the first to report on the application of the QPSO method to the GKSP. The efficiency of our proposed approach was tested on a large set of instances, and the results were compared to those produced by the commercial mixed integer programming solver CPLEX 12.5 of IBM-ILOG. The Experimental results demonstrated the good performance of the QPSO in solving the GKSP.     

Two-machine flowshop scheduling with bicriteria problem

This paper attempts to solve a two-machine flowshop bicriteria scheduling problem with release dates for the jobs, in which the objective function is to minimize a weighed sum of total flow time and makespan. To tackle this scheduling problem, an integer programming model with N²+3N variables and 5N constraints where N is the number of jobs, is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, a heuristic scheduling algorithm is presented. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. The average solution quality of the heuristic algorithm is above 99% and is much better than that of the SPT rule as a benchmark. A 15-job case requires only 0.018 s, on average, to obtain an ultimate or even optimal solution. The heuristic scheduling algorithm is a more practical approach to real world applications than the integer programming model.     

Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem

In this paper, we propose to solve the three‐dimensional single bin‐size bin packing problem (3D‐SBSBPP) using a simple strategy based on integer linear programming (ILP) heuristics, without using any improvement based on metaheuristics. We first propose an ILP that is converted into a series of three‐dimensional single knapsack problems (3D‐SKP). Then, the first tailored heuristic can be viewed as a hybrid approach in which both “selection” and “positioning” phases are combined. The first phase serves to select a subset of items where each of these items is susceptible to belonging to an active container. The positioning phase serves to pack a subset of items already preselected by the selection phase. Then, both phases cooperate till packing all items into their corresponding containers. The second heuristic can be viewed as an extended version of the first one. Indeed, before deciding whether the current container is closed or a new container is activated, “a local reoptimization phase” is considered. Finally, both proposed heuristics are evaluated on a set of random instances obtained by using the standard generator scheme of the literature. The provided results show that both proposed heuristics remain competitive when compared to the results obtained by one of the best methods of the literature.     

Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools

Several grammar-based genetic programming algorithms have been proposed in the literature to automatically generate heuristics for hard optimization problems. These approaches specify the algorithmic building blocks and the way in which they can be combined in a grammar; the best heuristic for the problem being tackled is found by an evolutionary algorithm that searches in the algorithm design space defined by the grammar.In this work, we propose a novel representation of the grammar by a sequence of categorical, integer, and real-valued parameters. We then use a tool for automatic algorithm configuration to search for the best algorithm for the problem at hand. Our experimental evaluation on the one-dimensional bin packing problem and the permutation flowshop problem with weighted tardiness objective shows that the proposed approach produces better algorithms than grammatical evolution, a well-established variant of grammar-based genetic programming. The reasons behind such improvement lie both in the representation proposed and in the method used to search the algorithm design space.     

A parallel multistart algorithm for the closest string problem

In this paper we describe and implement a parallel algorithm to find approximate solutions for the Closest String Problem (CSP). The CSP, also known as Motif Finding problem, has applications in Coding Theory and Computational Biology. The CSP is NP-hard which motivates us to think about heuristics to solve large instances. Several approximation algorithms have been designed for the CSP, but all of them have a poor performance guarantee. Recently some researchers have shown empirically that integer programming techniques can be successfully used to solve moderate-size instances (10–30 strings each of which is 300–800 characters long) of the CSP. However, real-world instances are larger than those tested. In this paper we show how a simple heuristic can be used to find near-optimal solutions to that problem. We implemented a parallel version of this heuristic and report computational experiments on large-scale instances. These results show the effectiveness of our approach.