Learning for efficient search

Learning for problem solving involves acquisition and storage of relevant knowledge from past problem solving instances in a domain in such a form that the information can be used to effectively solve subsequent problems in the same domain. Our interest is in the role of learning in problem solving systems that solve problems optimally. Such problems can be solved by an informed search algorithm like A*. Learning a stronger heuristic function leads to more effective problem solving. A set of arbitrary features of the domain induce a clustering of the state space. The heuristic information associated with each cluster may be learned. We discuss the use of a new form of information in the form ofh* set (the set of optimum cost values of all nodes of the cluster) and present an algorithm for using the information that is more effective than A*. A possibilistic (fuzzy set theoretic) extension of this algorithm is also presented. This version can handle incomplete information and is expected to find solutions faster in the average case with controlled relaxation in the optimality guarantee. We also discuss how to make the best use of the features, when the system has memory restrictions that limit the number of classes that can be stored.     

Heuristic algorithms for a storage location assignment problem in a chaotic warehouse

The extensive application of emerging technologies is revolutionizing warehouse management. These technologies facilitate working with complex and powerful warehouse management models in which products do not have assigned fixed locations (random storage). Random storage allows the utilization of the available space to be optimized. In this context, and motivated by a real problem, this article presents a model that looks for the optimal allocation of goods in order to maximize the storage space availability within the restrictions of the warehouse. For the proposed model a construction method, a local search algorithm and different metaheuristics have been developed. The introduced algorithms can also be used for other purposes such as to assess when and how it is convenient to perform relocation of stored items to improve the current level of storage space availability. Computational tests performed on a set of randomly generated and real warehouse instances show the effectiveness of the proposed methods.     

Modelling and a tabu search solution for the slab reallocation problem in the steel industry

This paper considers a slab reallocation problem arising from operations planning in the steel industry. The problem involves reallocating steel slabs to customer orders to improve the utilisation of slabs and the level of customer satisfaction. It can be viewed as an extension of a multiple knapsack problem. We firstly formulate the problem as an integer nonlinear programming (INLP) model. With variable replacement, the INLP model is then transformed into a mixed integer linear programming (MILP) model, which can be solved to optimality by MILP optimisers for very small instances. To obtain satisfactory solutions efficiently for practical-sized instances, a heuristic algorithm based on tabu search (TS) is proposed. The algorithm employs multiple neighbourhoods including swap, insertion and ejection chain in local search, and adopts solution space decomposition to speed up computation. In the ejection chain neighbourhood, a new and more effective search method is also proposed to take advantage of the structural properties of the problem. Computational experiments on real data from an advanced iron and steel company in China show that the algorithm generates very good results within a short time. Based on the model and solution approach, a decision support system has been developed and implemented in the company.     

An implementation of the iterated tabu search algorithm for the quadratic assignment problem

In this paper, we describe an implementation of the iterated tabu search (ITS) algorithm for the quadratic assignment problem (QAP), which is one of the well-known problems in combinatorial optimization. The medium- and large-scale QAPs are not, to this date, practically solvable to optimality, therefore heuristic algorithms are widely used. In the proposed ITS approach, intensification and diversification mechanisms are combined in a proper way. The goal of intensification is to search for good solutions in the neighbourhood of a given solution, while diversification is responsible for escaping from local optima and moving towards new regions of the search space. In particular, the following enhancements were implemented: new formula for fast evaluation of the objective function and efficient data structure; extended intensification mechanisms (including randomized tabu criterion, combination of tabu search and local search, dynamic tabu list maintaining); enhanced diversification strategy using periodic tabu tenure and special mutation procedure. The ITS algorithm is tested on the different instances taken from the QAP library QAPLIB. The results from the experiments demonstrate promising efficiency of the proposed algorithm, especially for the random QAP instances.     

Three perspectives for solving the job grouping problem

The production efficiency of printed circuit board (PCB) assembly depends strongly on the organization of the component placement jobs. This is characteristic, especially in a high-mix low-volume production environment. The present study discusses the problem of arranging the jobs of one machine into groups in such a way that the job change costs will be minimized when the costs depend on the number of the job groups. This problem is motivated by the practical case where the group utilizes a common machine set-up and the number of set-up occasions is the dominating factor in the production line optimization. The problem is well known and its large instances are hard to solve to optimality. We show how real-life problem instances can be solved by three different methods: efficient heuristics, 0/1-programming, and constraint programming. The first two of these are standard approaches in the field, whereas the application of constraint programming is new for the job grouping problem. The heuristic approach turns out to be efficient: algorithms are fast and produce optimal or nearly optimal groupings. 0/1-programming is capable of finding optimal solutions to small problem instances and it therefore serves as a benchmark to approximative methods. The constraint approach solves moderately large problem instances to optimality and it has the great advantage that changing the problem formulation is relatively easy one can add new constraints or modify the details of the existing ones flexibly.     

Solution algorithms for the number of tardy jobs minimisation scheduling with a time-dependent learning effect

This paper deals with a single-machine scheduling problem with a time-dependent learning effect. The goal is to determine the job sequence that minimise the number of tardy jobs. Two dominance properties, two heuristic algorithms and a lower bound to speed up the search process of the branch-and-bound algorithm are proposed. Computational experiments show that the branch-and-bound algorithm can solve instances up to 18 jobs in a reasonable amount of time, and the proposed heuristic algorithm MFLA performs effectively and efficiently     

A storage assignment policy in a man-on-board automated storage/retrieval system

This paper deals with a man-on-board automated storage/retrieval system where each customer order consists of a number of different items and is picked one at a time. For the system the problem examined is to allocate storage locations dedicatedly to items so that the total travel time required to pick all the given orders per period is minimized. The problem is shown to be formulated as a variant of the generalized assignment model. A heuristic for the storage layout problem is developed based on the group technology concept considering both order structure and frequency. Through the heuristic, close relationships between items are identified from the order structure, and then based on the relationships the items are compelled to be stored closely in the storage rack following a space-filling curve. Experimental results are provided to describe the performance of the heuristic     

Optimal and heuristic algorithms for the multi-location dynamic transshipment problem with fixed transshipment costs

We consider centrally controlled multi-location systems, which coordinate their replenishment strategies through the use of transshipments. In a dynamic deterministic demand environment the problem is characterized by several locations, each of which has known demand for a single product for each period in a given finite horizon. We consider replenishment, transshipment and inventory holding costs at each location, where the first two have location-dependent fixed, as well as linear components, and the third is linear and identical to all locations. We prove that the resulting dynamic transshipment problem is NP-hard, identify a special structure which is satisfied by an optimal solution and develop, based on this structure, an exponential time algorithm to solve the problem optimally. In addition, we develop a heuristic algorithm, based on partitioning the time horizon, which is capable of solving larger instances than the optimal solution. Our computational tests demonstrate that the heuristic performs extremely well.     

一种数据网格存储模型与并行下载调度算法

针对在数据网格中创建多副本虽可有效提升下载速度、降低网络流量,但多副本创建会带来大量存储开销和网络流量开销,以及基于GridFTP协议的各种并行下载算法虽可进一步提升下载速度,但仍不能解决多副本对存储空间和网络流量的影响的问题,提出了一个能保证数据的完整性、存储的可靠性和降低存储空间的数据网格存储模型,并基于该存储模型和GridFTP协议,提出了一个并行下载调度算法。实验表明,该算法只需要较少的冗余便可达到现有的针对全副本的并行下载算法可达到的理想下载速度,取得较好的效果,实现并行快速传输、节约存储空间和降低网络流量的目标。     

Heuristic and exact algorithms for the multi-pile vehicle routing problem

The multi-pile vehicle routing problem is a particular combination of loading and routing problems, in which items have to be loaded into different piles within vehicles, and then delivered with minimum cost. The problem is motivated by a real-world timber distribution problem, and is of both theoretical and practical interest. In this paper, we first develop heuristic and exact methods to solve the loading problem. We then include these methods into a tailored combination of Variable Neighborhood Search and Branch-and-Cut, to solve the overall problem. Extensive computational results show how the resulting algorithms are capable of solving to optimality a large number of small-size instances, and of consistently outperforming previous algorithms from the literature on large-size and real-world instances.     

Optimal search of distributed arrival time control

Distributed arrival time control (DATC) is a heuristic feedback control algorithm for scheduling which has been developed for a real-time distributed scheduling of heterarchical systems. It has been renowned not only for its fast solution searching algorithm but also for its flexibility to changing environment. However, the optimality of this heuristic method has not been analytically explained until recently because it has been designed to discover a near optimal solution instead of the true optimum. In this paper, we provide a novel optimal search method for the DATC scheduling problem by introducing a scalar cost function over the vector space of time and show the existence and location of true optima for the DATC scheduling problem through geometric approach. This geometrical interpretation enables us to find the true optimal by direct projection without iterations like previous DATC approaches. Based on the true optimum found, we evaluate the optimality of DATC algorithms by examining their dependency on initial conditions and explain their intrinsic causality mechanism for the discrepancy with true optimum. The implication of this study is on the new viewpoint over the vector space of DATC, which not only solves the optimality issue of DATC but also provides a new direction of direct search approach like projection method for the true optimum.     

Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints

This paper introduces models and algorithms for a static dial-a-ride problem arising in the transportation of patients by non-profit organizations such as the Austrian Red Cross. This problem is characterized by the presence of heterogeneous vehicles and patients. In our problem, two types of vehicles are used, each providing a different capacity for four different modes of transportation. Patients may request to be transported either seated, on a stretcher or in a wheelchair. In addition, some may require accompanying persons. The problem is to construct a minimum-cost routing plan satisfying service-related criteria, expressed in terms of time windows, as well as driver-related constraints expressed in terms of maximum route duration limits and mandatory lunch breaks. We introduce both a three-index and a set-partitioning formulation of the problem. The linear programming relaxation of the latter is solved by a column generation algorithm. We also propose a variable neighborhood search heuristic. Finally, we integrate the heuristic and the column generation approach into a collaborative framework. The column generation algorithm and the collaborative framework provide tight lower bounds on the optimal solution values for small-to-medium-sized instances. The variable neighborhood search algorithm yields high-quality solutions for realistic test instances.     

A heuristic travel time model for random storage systems using closest open location load dispatching

A heuristic method is proposed for estimating travel times in unit load random storage systems where incoming loads are dispatched to the closest available storage positions. A queuing model representation is used where servers correspond to storage positions and the service rate is based on the turnover distribution of stored loads. The resultant state distribution is applied to approximate storage position occupancy probabilities useful for generating storage and retrieval travel time estimates. Computational results suggest that the heuristic procedure yields smaller errors in random storage travel time estimates than alternative models.     

Pattern-set generation algorithm for the one-dimensional multiple stock sizes cutting stock problem

A pattern-set generation algorithm (PSG) for the one-dimensional multiple stock sizes cutting stock problem (1DMSSCSP) is presented. The solution process contains two stages. In the first stage, the PSG solves the residual problems repeatedly to generate the patterns in the pattern set, where each residual problem is solved by the column-generation approach, and each pattern is generated by solving a single large object placement problem. In the second stage, the integer linear programming model of the 1DMSSCSP is solved using a commercial solver, where only the patterns in the pattern set are considered. The computational results of benchmark instances indicate that the PSG outperforms existing heuristic algorithms and rivals the exact algorithm in solution quality.     

求解考虑顺序相关调整时间的双边装配线平衡问题的变邻域搜索算法

为有效解决带有顺序相关调整时间的双边装配线平衡问题,提出了一种简单高效的变邻域搜索算法。该算法通过将优先关系约束融入到交换、插入、交叉、变异等算子中,分别得到4个不同的邻域结构来保证搜索过程中解的可行性,避免过多重复邻域解的生成。4个邻域结构的搜索空间依次变大,以增强算法搜索能力。同时,结合装配线的特点,提出基于作业序列的编码和解码方式,在解码过程中,优先选择空闲时间较多的边,引入启发式目标加快算法收敛。分配结束后,对装配线末端的工作站组进行局部调整。通过将该算法先后用于求解无/有顺序相关调整时间的双边装配线平衡第一类问题,并与已有的算法进行对比,验证了所提的变邻域搜索算法的优越性和有效性。     

A flower pollination algorithm for the double-floor corridor allocation problem†

This research explores the double-floor corridor allocation problem (DFCAP), which deals with the optimal arrangement of departments over two floors and then place them along both sides against a corridor. This problem is a natural extension of the corridor allocation problem (CAP) to additional floors; the layout of each floor can be regarded as an approximately independent CAP. The DFCAP is commonly observed in manufacturing and service buildings. In this study, a mixed-integer programming formulation for the DFCAP is developed, and it is able to reduce to the classical CAP model. Then a novel flower pollination algorithm is provided, which is discretised using swap pair set approach to solve the considered DFCAP. In addition, to ameliorate the algorithm, three constructive heuristic rules are developed to produce a reasonably good initial population; meanwhile, a variable neighbourhood search structure is presented to prevent prematurity in arrival at a poor local solution. Finally, several instances for the DFCAP with a size of 9?≤?n?≤?80 are employed in the algorithms, as well as in mixed-integer non-linear programming (MINLP) formulations, which are solved with GUROBI 7.0.1. Moreover, the above-mentioned instances are utilized to show that the proposed algorithm performs better in comparison to the state-of-the-art optimization algorithms.     

Balancing transfer lines using Benders decomposition and ant colony optimisation techniques

In this paper, we investigate a transfer line balancing problem in order to find the line configuration that minimises the non-productive time. The problem is defined at an auto manufacturing company where the cylinder head is manufactured. Technological restrictions among design features and manufacturing operations are taken into consideration. The problem is represented by an integer programming model that assigns design features and cutting tools to machining stations, and specifies the number of machines and production sequence in each station. Three algorithms are developed to efficiently solve the problem under study. The first algorithm uses Benders decomposition approach that decomposes the proposed model into an assignment problem and a sequencing problem. The second algorithm is a hybrid algorithm that mixes Benders decomposition approach with the ant colony optimisation technique. The third algorithm solves the problem using two nested ant colonies. Using 15 different problem dimensions, we compare results of the three algorithms in a computational study. The first algorithm finds optimal solutions of small problem instances only. Second and third algorithms demonstrate optimality gaps less than 4.04 and 3.8%, respectively, when compared to the optimal results given by the first algorithm. Moreover, the second and third algorithms are very promising in solving medium and large-scale problem instances.     

Multiple-variable neighbourhood search for the single-machine total weighted tardiness problem

The single-machine total weighted tardiness (SMTWT) problem is a typical discrete combinatorial optimization problem in the scheduling literature. This problem has been proved to be NP hard and thus provides a challenging area for metaheuristics, especially the variable neighbourhood search algorithm. In this article, a multiple variable neighbourhood search (m-VNS) algorithm with multiple neighbourhood structures is proposed to solve the problem. Special mechanisms named matching and strengthening operations are employed in the algorithm, which has an auto-revising local search procedure to explore the solution space beyond local optimality. Two aspects, searching direction and searching depth, are considered, and neighbourhood structures are systematically exchanged. Experimental results show that the proposed m-VNS algorithm outperforms all the compared algorithms in solving the SMTWT problem.     

The generalised machine layout problem

The Generalised MAchine Layout Problem (GMALP) is a generalisation of the integrated machine and layout problem, which is an extension of the machine layout problem. More specifically, the GMALP is the designing of a facility layout by defining the product mix, selecting the number of machines to be used, assigning these machines to the plant floor, and assigning products to machines such that total profit is maximised. Moreover, the GMALP integrates the quadratic assignment problem with a multicommodity flow problem. Therefore, the GMALP is a computationally intractable problem. Consequently, a mixed-integer nonlinear programming model was developed and used to solve small problem instances. Also, two simple construction algorithms and a tabu search (TS) heuristic were developed for solving large GMALP instances in acceptable computation times. In addition, a test dataset was used to evaluate the performances of the TS heuristic using the different construction algorithms. The results show that the TS heuristic perform slightly better with the second construction algorithm.     

Line-seru conversion towards reducing worker(s) without increasing makespan: models,exact and meta-heuristic solutions

Compared with the traditional assembly line, seru production can reduce worker(s) and decrease makespan. However, when the two objectives are considered simultaneously, Pareto-optimal solutions may save manpower but increase makespan. Therefore, we formulate line-seru conversion towards reducing worker(s) without increasing makespan and develop exact and meta-heuristic algorithms for the different scale instances. Firstly, we analyse the distinct features of the model. Furthermore, according to the feature of the solution space, we propose two exact algorithms to solve the small to medium-scale instances. The first exact algorithm searches the solution space from more workers to fewer workers. The second exact algorithm searches the solution space from fewer workers to more workers. The two exact algorithms search a part of solution space to obtain the optimal solution of reducing worker(s) without increasing makespan. According to the variable length of the feasible solutions, we propose a variable-length encoding heuristic algorithm for the large-scale instances. Finally, we use the extensive experiments to evaluate the performance of the proposed algorithms and to investigate some managerial insights on when and how to reduce worker(s) without increasing makespan by line-seru conversion.