Probabilistic behaviour of optical bin-packing solutions

The bin-packing problem is studied from a probabilistic view point. It is shown that, when the sizes of the n elements to be packed are drawn independently from a probability distribution F, then the minimum number of bins necessary for the packing of these n elements is asymptotically (a.e.) proportional to n in three cases. In all three cases, the constant of proportionality to n is explicitly given. Furthermore, in two of the cases, a heuristic is described which is asymptotically almost surely closed to the optimal solution.     

Fix and Relax Heuristic for a Stochastic Lot-Sizing Problem

This paper addresses a particular stochastic lot-sizing and scheduling problem. The evolution of the uncertain parameters is modelled by means of a scenario tree and the resulting model is a multistage stochastic mixed-integer program. We develop a heuristic approach that exploits the specific structure of the problem. The computational experiments carried out on a large set of instances have shown that the approach provides good quality solutions in a reasonable amount of time.     

Global optimization with a limited solution time

In this paper the box constrained global optimization problem in presence of a limited solution time is considered. A method is studied based on a combination of multistart and singlestart which implies a decision sequence on the number of random points to be generated. Search strategies are numerically illustrated. Criteria are introduced to measure the performance of solution methods for the problem class. Moreover, the performance of search strategies, specifically the efficiency of generating random points is analyzed.     

An Optimization Model to Determine Master Designs and Runs for Advertisement Printing

In this paper we consider a common optimization problem faced by a printing company while designing masters for advertisement material. A printing company may receive from various customers, advertisements for their products and services and their demand is for a specified number of copies to be printed. In a particular case, the printer receives these orders to be delivered next week from the customers, until the Thursday of a week. By Monday the printed copies have to be delivered to the customers. These advertisement items of the various customers are to be printed on large sheets of papers of specified standard sizes. The size is called a k-up if k items can be printed on one sheet. It is a given constraint that only items of the same size can be loaded on a master. This constraint results in a decomposition of the original problem of designing masters into many sub-problems, one for each size. The objective is to minimize the number of masters required while meeting the requirements of the customers. We formulate this optimization problem mathematically, discuss the computational issues and present some heuristic approaches for solving the problem.     

An efficient method to determine the optimal configuration of a flexible manufacturing system

A frequently encountered design issue for a flexible manufacturing system (FMS) is to find the lowest cost configuration, i.e. the number of resources of each type (machines, pallets, ...), which achieves a given production rate. In this paper, an efficient method to determine this optimal configuration is presented. The FMS is modelled as a closed queueing network. The proposed procedure first derives a heuristic solution and then the optimal solution. The computational complexity for finding the optimal solution is very reasonable even for large systems, except in some extreme cases. Moreover, the heuristic solution can always be determined and is very close (and often equal) to the optimal solution. A comparison with the previous method of Vinod and Solberg shows that our method performs very well.     

Experimental studies of variable selection strategies based on constraint weights

Variable ordering heuristics that sample information before or during search in order to inform subsequent decisions have shown better performance and greater robustness than standard heuristics. One such strategy, the “weighted degree heuristic,” is based on weighting constraints according to their involvement in failure during search. A more recent approach uses “random probing” with restarting to gain information less subject to sampling bias. To date, these approaches have not been carefully analysed experimentally. In the present work, several important findings are presented, including a better delineation of the class of events that is sampled, an analysis of the importance of informed choices at the beginning of search, and a demonstration that random probing identifies sources of global contention effectively even when these are not clearly demarcated. These experiments show how empirical analysis can clarify subtle issues in the analysis of heuristic procedures for difficult search problems.     

New TSP Construction Heuristics and Their Relationships to the 2-Opt

Correction heuristics for the traveling salesman problem (TSP), with the 2-Opt applied as a postprocess, are studied with respect to their tour lengths and computation times. This study analyzes the 2-Opt dependency, which indicates how the performance of the 2-Opt depends on the initial tours built by the construction heuristics. In accordance with the analysis, we devise a new construction heuristic, the recursive-selection with long-edge preference (RSL) method, which runs faster than the multiple-fragment method and produces a comparable tour when they are combined with the 2-Opt.     

A setup heuristic for interval orders

The setup minimization problem for linear extensions of interval orders is considered and a simple greedy heuristic is shown to be never worse than twice the optimum.     

(k,c) – coloring via Column Generation

In this paper we study the (k,c) – coloring problem, a generalization of the well known Vertex Coloring Problem (VCP). We propose a new formulation and compare it computationally with another formulation from the literature. We also develop a diving heuristic that provides with good quality results at a reasonable computational effort.     

Clustering for routing in densely populated areas

This paper introduces a new approach for generating school bus routes in a dense urban area. First, a districting algorithm is used to determine clusters including appropriate numbers of students. Then, for each cluster, a route and the stops along this route are determined. Numerical results are reported and compared with those obtained previously. Although the algorithm has been developped and tested in a specific context, it could easily be extended to more general vehicle routing problems.     

Worst-case analysis of a scheduling algorithm

In this note, a heuristic proposed by Ibarra and Kim (IK) for scheduling independent tasks on unrelated processors is analyzed. The heuristic may create a schedule which finishes a time $\text{m 1 OPT}$, where m is the number of processors, and OPT is the time used in the optimal schedule. This compares unfavorably with the heuristics described by Davis and Jaffe [2], which have worst-case behavior which is $\text{O(OPT 1 m}{}^{0.5}\text{)}$.     

A parallel insert method for the capacitated arc routing problem

The arc routing problem involves the total distance covered in traversing a certain number of arcs in a network. In the capacitated version of this problem of a finite capacity is associated with each vehicle. In this paper we introduce a new approximate solution strategy for the capacitated arc routing problem (CARP). This strategy usesd an insertion procedure to generate many routes in parallel. The purpose is to obtain a better balance between the costs of each route. Computational results are reported.     

Metaheuristics for the team orienteering problem

The Team Orienteering Problem (TOP) is the generalization to the case of multiple tours of the Orienteering Problem, known also as Selective Traveling Salesman Problem. A set of potential customers is available and a profit is collected from the visit to each customer. A fleet of vehicles is available to visit the customers, within a given time limit. The profit of a customer can be collected by one vehicle at most. The objective is to identify the customers which maximize the total collected profit while satisfying the given time limit for each vehicle. We propose two variants of a generalized tabu search algorithm and a variable neighborhood search algorithm for the solution of the TOP and show that each of these algorithms beats the already known heuristics. Computational experiments are made on standard instances.     

半讨厌型设施选址问题的模型与算法

研究了结合网络和平面模型的半讨厌型设施的选址问题.半讨厌型设施结合了讨厌型设施与喜爱型设施的性质,一方面由于这些设施对人们带来很多副作用,人们想要远离他们以避免遭到污染,但同时人们又希望距离设施不要过远,因此建立0-1整数模型,在保证所有人使用该设施的距离不超过既定距离的基础上,使污染范围最小.由于该问题是NP困难问题,本为给出了启发式算法,通过算例进行了比较分析,证明了算法的有效性.     

A family of genetic algorithms for the pallet loading problem

This paper is concerned with a family of genetic algorithms for the pallet loading problem. Our algorithms differ from previous applications of genetic algorithms to two-dimensional packing problems in that our coding contains all the information needed to produce the packing it represents, rather than relying on a packing algorithm to decode each individual solution. We experiment with traditional one-dimensional string representations, and a two-dimensional matrix representation which preserves the notion of closeness between positions on the pallet. Two new crossover operators are introduced for the two-dimensional case. Our definition of solution space includes both feasible and infeasible solutions and we suggest a number of different fitness functions which penalise infeasibility in different ways and a repair operator which allows our populations to maintain feasibility. The results of experiments designed to test the effectiveness of these features are presented.     

资源有限网络计划启发式方法的评价（中）：启发式方法的综合比较和评价

通过设计评价启发式方法优劣效果的度量指标——工期比率、比率和及差值率,利用随机活动网络发生器产生的５０ 个网络计划,对最常用的３１ 种资源有限网络计划的启发式方法的总体效果进行了比较、分析、评价和排序,便于人们在使用启发式方法之前,就可以预知该方法的大致效果,估计可能引起的偏差,在满足实际需要的前提下,选择合适的启发式方法。     

资源有限网络计划的PRWI启发式优化方法

本文在综合考虑了有资源约束的网络计划结构特征、资源强度、时间约束等方面因素的基础上，提出了一种新的资源优化的启发式优化方法—ＰＲＷＩ方法，并通过分析证明了该方法处理问题的效果较现有的其它方法好。     

关于大学课程表问题的研究

大学课程表问题可以表述为：如何为给定的一组课程编排一个时间表，以使得所有的学生选课要求都得到满足，并且这些课程所用的不同课时段数目最少。在本中我们首先证明了即使每位学生最多选两门课程，该问题仍然是NP-难解的，然后我们提出了求解该问题一般情形的一个启发式算法。     

A Heuristic for Boolean Optimization Problems

A heuristic method is proposed for the solution of a large class of binary optimization problems, which includes weighted versions of the set covering, graph stability, partitioning, maximum satisfiability, and numerous other problems. The reported substantial computational experiments amply demonstrate the efficiency of the proposed method.