BIDPS^＊：基本的循环加深周边搜索算法

ＢＩＤＰＳ＾＊是一种把ＩＤＡ算法和ＰＳ法相结合而产生的人工智能搜索算法。该文研究了不考虑启发式计算最小化技术的搜索效率问题，提出了一些新的算法效率的度量，用８数码难题检验了ＢＩＤＰＳ算法并与ＩＤＡ算法进行了比较分析，实验结果表明尽管ＢＩＤＰＳ启发式计算量较大，但较ＩＤＡ算法在效率上还有所提高的。     

Efficient primal-dual heuristic for a dynamic location problem

In this paper the dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal-dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal-dual heuristic based on the work of Erlenkotter [A dual-based procedure for uncapacitated facility location. Operations Research 1978;26:992–1009] and Van Roy and Erlenkotter [A dual-based procedure for dynamic facility location. Management Science 1982;28:1091–105] was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated as in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.     

Order acceptance with weighted tardiness

Over the past decade the strategic importance of order acceptance has been widely recognized in practice as well as academic research. This paper examines order acceptance decisions when capacity is limited, customers receive a discount for late delivery, but early delivery is neither penalized nor rewarded. We model a manufacturing facility that considers a pool of orders, and chooses for processing the subset that results in the highest profit. We present several solution methods, beginning with a straightforward application of an approach which separates sequencing and job acceptance. We then develop an optimal branch-and-bound procedure that uses a linear (integer) relaxation for bounding and performs the sequencing and job acceptance decisions jointly. We develop a variety of fast and high-quality heuristics based on this approach. For small problems, beam search runs almost 20 times faster than the benchmark, with a high degree of accuracy, and a branch-and-bound heuristic using Vogel's method for bounding is over 100 times faster with very high accuracy. For larger problems, a myopic heuristic based on the relaxation runs 2000 times faster than the beam-search benchmark, with comparable accuracy.     

An LP-based heuristic procedure for the generalized assignment problem with special ordered sets

The generalized assignment problem with special ordered sets (GAPS2), is the problem of allocating n tasks to m time-periods, where each task must be assigned to a time-period, or shared between two consecutive time-periods. For reasonably large values of m and n the NP-hard combinatorial problem GAPS2 becomes intractable for standard mathematical programming software, hence there is a need for heuristic algorithms to solve such problems. It will be shown how an LP-based heuristic developed previously for the well-established generalized assignment problem can be modified and extended to solve GAPS2. Encouraging results, in terms of speed and accuracy, in particular when compared to an existing heuristic for GAPS2, are described.     

A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems

In this paper we develop and compare several heuristic methods for solving the general two-dimensional cutting stock problem. We follow the Gilmore-Gomory column generation scheme in which at each iteration a new cutting pattern is obtained as the solution of a subproblem on one stock sheet. For solving this subproblem, in addition to classical dynamic programming, we have developed three heuristic procedures of increasing complexity, based on GRASP and Tabu Search techniques, producing solutions differing in quality and in time requirements. In order to obtain integer solutions from the fractional solutions of the Gilmore-Gomory process, we compare three rounding procedures, rounding up, truncated branch and bound and the solution of a residual problem. We have coded and tested all the combinations of algorithms and rounding procedures. The computational results obtained on a set of randomly generated test problems show their relative efficiency and allow the potential user to choose from among them, according to the available computing time. Rceived: January 9, 2001 / Accepted: December 10, 2001     

Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines

We consider the scheduling of orders in an environment with m uniform machines in parallel. Each order requests certain amounts of k different product types. Each product type can be produced by any one of the m machines. No setup is required if a machine switches over from one product type to another. Different product types intended for the same order can be produced at the same time (concurrently) on different machines. Each order is released at time zero and has a positive weight. Preemptions are allowed. The completion time of an order is the finish time of the product type that is completed last for that order. The objective is to minimize the total weighted completion time. We propose heuristics for the non-preemptive as well as the preemptive case and obtain worst case bounds that are a function of the number of machines as well as the differences in the speeds of the machines. Even though the worst-case bounds we showed for the two heuristics are not very tight, our experimental results show that they yield solutions that are very close to optimal.     

Nonnegative integral subset representations of integer sets

We consider an integer-subset representation problem motivated by a medical application in radiation therapy. We prove NP-completeness, derive nontrivial bounds, and report on the performance of a greedy heuristic.     

Response time variability

Response time variability is a new optimization problem with a broad range of applications and a distinctive number of theoretic flavour. The problem occurs whenever events, jobs, clients or products need to be sequenced so as to minimize the variability of time for which they wait for the next turn in obtaining the resources necessary for their advance. The problem has numerous real-life applications. We study its computational complexity, present efficiency, polynomial time algorithms for some cases, and the NP-hardness proof for a general problem. We propose a position exchange heuristic and apply it to improve the total response time variability of an initial sequence. The latter is the optimum bottleneck sequence, Webster or Jefferson sequence of the apportionment, or a random sequence. We report on computational experiments with the heuristic.     

A scheduling decision aid in glass fiber manufacturing

A decision aid for scheduling production in glass fiber manufacturing industry is described. The methodology combines a linear programming (LP) optimization model with a heuristic model. The LP model determines production goals; the heuristic model then uses the LP output to incorporate system-specific constraints in developing processing sequences.     

A domain-specific knowledge-based heuristic for the Blocks Relocation Problem

The Blocks Relocation Problem consists in minimizing the number of movements performed by a gantry crane in order to retrieve a subset of containers placed into a bay of a container yard according to a predefined order. A study on the mathematical formulations proposed in the related literature reveals that they are not suitable for its solution due to their high computational burden. Moreover, in this paper we show that, in some cases, they do not guarantee the optimality of the obtained solutions. In this regard, several optimization methods based on the well-known A¹ search framework are introduced to tackle the problem from an exact point of view. Using our A¹ algorithm we have corrected the optimal objective function value of 17 solutions out of 45 instances considered by Caserta et al. (2012) [4]. In addition, this work presents a domain-specific knowledge-based heuristic algorithm to find high-quality solutions by means of short computational times. It is based on finding the most promising positions into the bay where to relocate those containers that are currently located on the next one to be retrieved, in such a way that, they do not require any additional relocation operation in the future. The computational tests indicate the higher effectiveness and efficiency of the suggested heuristic when solving real-world scenarios in comparison with the most competitive approaches from the literature.