A heuristic multi-start decomposition approach for optimal design of serial machining lines

We study an optimal design problem for serial machining lines. Such lines consist of a sequence of stations. At every station, the operations to manufacture a product are grouped into blocks. The operations within each block are performed simultaneously by the same spindle head and the blocks of the same station are executed sequentially. The inclusion and exclusion constraints for combining operations into blocks and stations as well as the precedence constraints on the set of operations are given. The problem is to group the operations into blocks and stations minimizing the total line cost. A feasible solution must respect the given cycle time and all given constraints. In this paper, a heuristic multi-start decomposition approach is proposed. It utilizes a decomposition of the initial problem into several sub-problems on the basis of a heuristic solution. Then each obtained sub-problem is solved by an exact algorithm. This procedure is repeated many times, each time it starts with a new heuristic solution. Computational tests show that the proposed approach outperforms simple heuristic algorithms for large-scale problems.     

An improved heuristic for the far from most strings problem

The Far From Most Strings Problem (FFMSP) asks for a string that is far from as many as possible of a given set of strings. All the input and the output strings are of the same length, and two strings are far if their Hamming distance is greater than or equal to a given threshold. FFMSP belongs to the class of sequence consensus problems which have applications in molecular biology, amongst others. FFMSP is NP-hard. It does not admit a constant-ratio approximation either, unless P=NP. In the last few years, heuristic and metaheuristic algorithms have been proposed for the problem, which use local search and require a heuristic, also called an evaluation function, to evaluate candidate solutions during local search. The heuristic function used, for this purpose, in these algorithms is the problem’s objective function. However, since many candidate solutions can be of the same objective value, the resulting search landscape includes many points which correspond to local maxima. In this paper, we devise a new heuristic function to evaluate candidate solutions. We then incorporate the proposed heuristic function within a Greedy Randomized Adaptive Search Procedure (GRASP), a metaheuristic originally proposed for the problem by Festa. The resulting algorithm outperforms state-of-the-art with respect to solution quality, in some cases by orders of magnitude, on both random and real data in our experiments. The results indicate that the number of local optima is considerably reduced using the proposed heuristic.     

An Iterative Construction Heuristic for the Ore Selection Problem

The ore selection problem involves choosing a processing option for a number of mining blocks that maximises the expected payoff for a given level of financial risk. An innovative neighbourhood search heuristic is proposed for the ore selection problem. This iterative construction heuristic employs a stochastic demolition and reconstruction strategy. Computational experiments with this heuristic for two ore selection problem instances, one involving 2,500 blocks and the other involving 78,000 blocks, are given. These problem instances are made publicly available for use by future workers. Our computational experiments indicate that the proposed heuristic produces better quality solutions faster than a relay hybrid (constructive-simulated annealing) heuristic.     

求解系统可靠性优化中指派问题的启发式算法

本文回顾了系统可靠性优化中部件指派问题的研究,针对该类问题特点提出了一个新的启发式算法,该算法基于概率重要度来指派部件可靠度。文章最后给出了算例分析,并将算法结果与已有的算法和枚举法求得的最优解进行了比较。新的算法简单,而且效率非常高,可以在很短的计算时间内得到较好的求解效果,有效提高了复杂系统和大规模系统可靠性优化的计算效率。     

Single facility scheduling with multiple job classes

This paper considers a static single facility scheduling problem where jobs are divided into several mutually exclusive classes. The jobs in a given class need not be processed together. In addition to a known processing time for each job, there is a switching time involved which depends on the class of the job immediately preceding a job. A heuristic algorithm is proposed to find a minimum mean flow time schedule. The effectiveness of the proposed heuristic algorithm is empirically evaluated and found to indicate that the solutions obtained from this heuristic algorithm are often close to optimal.     

An investigation into the relationship of heuristic performance with network-resource characteristics

Constrained resource project management heuristics are analyzed and their performance is assessed related to well defined project types. Such results have shown that using the overall performance measure of a given heuristic can, in some situations, be misleading.An efficient heuristic, which combines resource and criticality factors is also proposed. Computational experiments on a set of 6120 networks varying in size from 45–666 activities, 3 resources, and under different network parameters are reported. The proposed heuristic outperforms the best existing dispatching rules in certain project classes and also on problem sets appearing in the literature.     

A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls

We consider an extension of the capacitated Vehicle Routing Problem (VRP), known as the Vehicle Routing Problem with Backhauls (VRPB), in which the set of customers is partitioned into two subsets: Linehaul and Backhaul customers. Each Linehaul customer requires the delivery of a given quantity of product from the depot, whereas a given quantity of product must be picked up from each Backhaul customer and transported to the depot. VRPB is known to be NP-hard in the strong sense, and many heuristic algorithms were proposed for the approximate solution of the problem with symmetric or Euclidean cost matrices. We present a cluster-first-route-second heuristic which uses a new clustering method and may also be used to solve problems with asymmetric cost matrix. The approach exploits the information of the normally infeasible VRPB solutions associated with a lower bound. The bound used is a Lagrangian relaxation previously proposed by the authors. The final set of feasible routes is built through a modified Traveling Salesman Problem (TSP) heuristic, and inter-route and intra-route arc exchanges. Extensive computational tests on symmetric and asymmetric instances from the literature show the effectiveness of the proposed approach.     

Offsetting inventory replenishment cycles to minimize storage space

In a recent paper, [Murthy, N.N., Benton, W.C., Rubin, P.A., 2003. Offsetting inventory cycles of items sharing storage. European Journal of Operational Research 150, 304–319] discussed the problem of offsetting inventory replenishment cycles of several items in order to minimize the maximum required storage space. They analyzed the case where replenishment cycles are given integer multiples of a basic period and proposed a heuristic to solve the problem. While they provided a good analysis of the considered problem, the proposed heuristic produces less interesting results. In the following, a simpler, more efficient and easier to implement heuristic is proposed. Numerical results are provided to prove its superiority.     

A heuristic algorithm for the strip packing problem

The two-dimensional strip packing problem is to pack a given set of rectangles into a strip with a given width and infinite height so as to minimize the required height of the packing. From the computational point of view, the strip packing problem is an NP-hard problem. With the B*-tree representation, this paper first presents a heuristic packing strategy which evaluates the positions used by the rectangles. Then an effective local search method is introduced to improve the results and a heuristic algorithm (HA) is further developed to find a desirable solution. Computational results on randomly generated instances and popular test instances show that the proposed method is efficient for the strip packing problem.     

A Multiple-rule Heuristic for Assembly Line Balancing

This paper introduces a four-rule heuristic method for production/assembly line balancing which seeks to minimize the number of workstations for a given cycle time. To evaluate its performance, the proposed method was compared with 15 other heuristic methods ranging in complexity from random assignment of work elements to Hoffmann's enumeration procedure. The results, based on both randomly generated problems and problems taken from the literature, indicate that the proposed heuristic outperformed other procedures. Further, the suggested method was able to find the optimal solution for 57 (85%) of the 67 literature problems.     

An efficient algorithm to allocate shelf space

Shelf space is one of the most important resources of a retail firm. This paper formulates a model and proposes an approach which is similar to the algorithm used for solving a knapsack problem. Subject to given constraints, the proposed heuristic allocates shelf space item by item according to a descending order of sales profit for each item per display area or length. Through the use of simulations, the performances of objective value and the computational efficiency of this method are evaluated. Three options are also proposed for improving the heuristics. Compared to an optimal method, the improved heuristic is shown to be a very efficient algorithm which allocates shelf space at near-optimal levels.     

Discontinuous Local Delivery Costs Re-Examined

The problem of locating depots when discontinuities occur in the local delivery cost function has been examined before and a heuristic procedure proposed. Here, an alternative search procedure, which can be used in conjunction with the previous heuristic, is described leading to the development of a family of heuristics. Some of these are tested and the results given. Conclusions are then drawn as to the best procedure to use under different circumstances.     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.     

A Self-Adjusting Algorithm for Driver Scheduling

Public transport driver scheduling is a world wide problem, which is NP-hard. Although some mathematically based methods are being used in the transport industry, there is still much scope for improvements. This paper presents a novel evolutionary approach that simulates the self-adjusting process on a single schedule. Five factors characterized by fuzzy membership functions are first aggregated to evaluate the shift structure. This evaluating function is incorporated into a constructing heuristic to make shift selection. A self-adjusting algorithm is then designed to guide the constructing heuristic to improve a given initial schedule iteratively. In each generation an unfit portion of the working schedule is removed. Broken schedules are repaired by the constructing heuristic until stopping condition is met. Experimental results on real-world driver scheduling problems has demonstrated the success of the proposed approach.     

Network flow-based approaches for integrated aircraft fleeting and routing

Given a schedule of flights to be flown, the aircraft fleeting and routing problem (AFRP) consists of determining a minimum-cost route assignment for each aircraft so as to cover each flight by exactly one aircraft while satisfying maintenance requirements and other activity constraints. We investigate network flow-based heuristic approaches for this problem. Computational experiments conducted on real-data given by TunisAir show that the proposed heuristic consistently yields very near-optimal solutions while requiring modest CPU effort.     

An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs

The problem of scheduling in a flowshop is considered with the objective of minimizing the total weighted flowtime of jobs. A heuristic algorithm is developed by the introduction of lower bounds on the completion times of jobs and the development of heuristic preference relations for the scheduling problem under study. An improvement scheme is incorporated in the heuristic to enhance the quality of its solution. The proposed heuristic, with and without the improvement scheme, and the existing heuristics are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that both versions of the proposed heuristic perform better than the existing heuristics in giving a superior solution quality and that the proposed heuristic without the improvement scheme yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the proposed heuristic and the existing heuristics, as well as the effectiveness of a variant of the scheme. The results are also discussed.     

基于双重视角的MPPSP及其禁忌搜索启发式算法

首先界定研究假设条件并定义文中所使用的符号;随后从业主及承包商双重视角构建MPPSP的整数规划优化模型;针对问题的强NP-hard属性,设计禁忌搜索启发式算法;在随机生成的标准算例集合上对算法进行测试;最后用一个算例对研究结果进行说明。结论如下:本文所开发的禁忌搜索启发式算法可以有效地求解MPPSP;关于给定项目的支付进度安排,承包商和业主的偏好存在显著差异;随着支付次数与支付比例的增加,承包商收益提高,业主收益下降,而双方收益均随折现率的上升而下降。     

建筑废料现场分拣协调调度优化研究

工程项目施工现场废料分拣的效率对施工进度具有重要的影响。通过分析现场废料分拣实施过程,建立了带有限中间缓冲的混合流水车间调度模型。提出了收集阶段作业排序的动态自适应算法和后续设备分配问题的考虑缓冲区的设备分配规则,在此基础上设计了废料分拣模型的启发式算法,平衡各分区工作量,进一步搜索最优解,并推导了问题的一个低界。实验结果表明,所提出算法能很好地对施工现场废料分拣问题进行求解,具有良好的收敛性和较高的时间效率。     

Scheduling multi-stage parallel-processor services to minimize average response time

The problem of scheduling on a multi-stage parallel-processor architecture in computer centres is addressed with the objective of minimizing average completion time of a set of requests. The problem is modelled as a flexible flowshop problem for which few heuristics exist in the flowshop scheduling literature. A new three-phase heuristic is proposed in this paper. An extensive computational experiment has been conducted to compare the performance of the existing heuristics and the proposed heuristic. The results indicate that the proposed heuristic significantly outperforms the existing ones. More specifically, the overall average error of the best existing heuristic is about five times that of the proposed heuristic while the overall average CPU time of the proposed heuristic is about half of the best existing one. More importantly, as the number of requests increases, the CPU time of the proposed heuristic decreases considerably (compared to the best existing heuristic) while the ratio of the error (of the best existing to the proposed heuristic) of about five times remains almost the same.     

A breadth-first search applied to the minimization of the open stacks

This paper presents a heuristic for the minimization of the open stacks problem (MOSP). The proposed heuristic is based on a simple breadth-first search in MOSP graphs and two new greedy rules to overcome errors. The performance of the proposed heuristic is compared with the best exact and heuristic methods available in the literature. The results show that in addition to the suggested heuristic having much shorter running times than the exact algorithm, the error gap between them is small for a substantial proportion of almost 4500 benchmark instances taken from the literature. The proposed heuristic also has a more robust behaviour than the best heuristic for the MOSP, although less accurate. The proposed heuristic therefore constitutes a viable and cost-effective alternative for solving or obtaining good upper bounds for the MOSP.