Parallel hyper heuristic algorithm based on reinforcement learning for the corridor allocation problem and parallel row ordering problem

Hyper heuristics is a relatively new optimisation algorithm. Numerous studies have reported that hyper heuristics are well applied in combinatorial optimisation problems. As a classic combinatorial optimisation problem, the row layout problem has not been publicly reported on applying hyper heuristics to its various sub-problems. To fill this gap, this study proposes a parallel hyper-heuristic approach based on reinforcement learning for corridor allocation problems and parallel row ordering problems. For the proposed algorithm, an outer layer parallel computing framework was constructed based on the encoding of the problem. The simulated annealing, tabu search, and variable neighbourhood algorithms were used in the algorithm as low-level heuristic operations, and Q-learning in reinforcement learning was used as a high-level strategy. A state space containing sequences and fitness values was designed. The algorithm performance was then evaluated for benchmark instances of the corridor allocation problem (37 groups) and parallel row ordering problem (80 groups). The results showed that, in most cases, the proposed algorithm provided a better solution than the best-known solutions in the literature. Finally, the meta-heuristic algorithm applied to three low-level heuristic operations is taken as three independent algorithms and compared with the proposed hyper-heuristic algorithm on four groups of parallel row ordering problem instances. The effectiveness of Q-learning in selection is illustrated by analysing the comparison results of the four algorithms and the number of calls of the three low-level heuristic operations in the proposed method.     

Using dynamic demand information and zoning for the storage of non-uniform density stock keeping units

The warehouse order-picking operation is one of the most labour-intense activities that has an important impact on responsiveness and efficiency of the supply chain. An understanding of the impact of the simultaneous effects of customer demand patterns and order clustering, considering physical restrictions in product storage, is critical for improving operational performance. Storage restrictions may include storing non-uniform density stock keeping units (SKUs) whose dimensions and weight constrain the order-picking operation given that a priority must be followed. In this paper, a heuristic optimisation based on a quadratic integer programming is employed to generate a layout solution that considers customer demand patterns and order clustering. A simulation model is used to investigate the effects of creating and implementing these layout solutions in conjunction with density zones to account for restrictions in non-uniform density SKUs. Results from combining layout optimisation heuristics and density zoning indicate statistical significant differences between assignments that ignore the aforementioned factors and those that recognise it.     

Dynamic admission control for two customer classes with stochastic demands and strict due dates

We study a dynamic capacity allocation problem with admission control decisions of a company that caters for two demand classes with random arrivals, capacity requirements and strict due dates. We formulate the problem as a Markov decision process (MDP) in order to find the optimal admission control policy that maximises the expected profit of the company. Such a formulation suffers a state-space explosion. Moreover, it involves an additional dimension arising from the multiple possible order sizes that customers can request which further increases the complexity of the problem. To reduce the cardinality of possible policies, and, thus, the computational requirements, we propose a threshold-based policy. We formulate an MDP to generate such a policy. To deal with the curse of dimensionality, we develop threshold-based approximate algorithms based on the state-reduction heuristics with aggregation proposed previously. Our results reveal that for the majority of instances considered the optimal policy has a threshold structure. We then demonstrate the superiority of the proposed threshold-based approximate algorithms over two benchmark policies in terms of the generated profits and the robustness of the solutions to changes in operational conditions. Finally, we show that our proposed policies are also robust to changes in actual demand from its estimation.     

简单案例为主线的教学模式在C语言教学中的应用

本文通过分析C语言教学中存在的问题,提出以简单案例为主线的教学模式在C语言教学中有着积极的作用,并以在实际教学中采用的一个简单案例为例,详细介绍了在学习顺序结构、选择结构、函数、指针等相关内容的具体应用。实践证明,该教学方法能充分调动学生的积极性和主动性。     

Optimization of quality and operational costs through improved scheduling of harvest operations

The agriculture sector still lacks the tools and models to enhance the utilization of different resources. This paper addresses the vineyard harvesting problem in developing countries, with the objective of optimizing the wine quality and minimizing the operational costs. Heuristics were introduced to better assign the harvesting days to the different grape blocks that exist in the vineyard's field. The quality of the grapes was a key target as it can transform production from a pinnacle wine to a bulk one. We solved several numerical examples for verification and demonstrative purposes and found that our proposed approach finds solutions that significantly reduce the harvesting costs in the vineyard and considerably outperform Branch and Bound algorithm especially for large problems.     

Look-ahead heuristics for the dynamic traveling purchaser problem

Given a set of products each with positive discrete demand, and a set of markets selling products at given prices, the traveling purchaser problem (TPP) looks for a tour visiting a subset of markets such that products demand is satisfied at minimum purchasing and traveling costs. In this paper we analyze a dynamic variant of the problem, where quantities may decrease as time goes on. Complete information is assumed on current state of the world, i.e. decision maker knows quantities available for each product in each market at present time and is informed about any consumption event when it occurs. Nevertheless, planner does not have any information on future events. Two groups of heuristics are described and compared. The first group consists of simplified approaches deciding which market to visit next on the basis of some greedy criteria considering only one of the two objective costs. The second one includes heuristics based on a look-ahead approach taking into account both traveling and purchasing costs and inserting some future prediction. Heuristics behavior has been tested on a large set of randomly generated instances under different levels of dynamism.     

New simple and efficient heuristics for the uncapacitated single allocation hub location problem

Hub-and-spoke networks are widely studied in the area of location theory. They arise in several contexts, including passenger airlines, postal and parcel delivery, and computer and telecommunication networks. Hub location problems usually involve three simultaneous decisions to be made: the optimal number of hub nodes, their locations and the allocation of the non-hub nodes to the hubs. In the uncapacitated single allocation hub location problem (USAHLP) hub nodes have no capacity constraints and non-hub nodes must be assigned to only one hub. In this paper, we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve this problem. With multi-start heuristics, several different initial solutions are constructed and then improved by tabu search, while in the two-stage integrated heuristic tabu search is applied to improve both the locational and allocational part of the problem. Computational experiments using typical benchmark problems (Civil Aeronautics Board (CAB) and Australian Post (AP) data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. We also report the integer optimal solutions for all 80 CAB data set instances and the 12 AP instances up to 100 nodes, as well as for the corresponding new generated AP instances with reduced fixed costs.     

Finding non-dominated bicriteria shortest pairs of disjoint simple paths

In this paper we introduce a method to compute non-dominated bicriteria shortest pairs, each including two disjoint simple paths. The method is based on an algorithm for ranking pairs of disjoint simple paths by non-decreasing order of cost, that is an adaptation of a path ranking algorithm applied to a network obtained from the original one after a suitable modification of the topology. Each path in this new network corresponds to a pair of paths in the former one. Computational results are presented and analysed for randomly generated networks.     

Genetic algorithm-based heuristics for an open shop scheduling problem with setup,processing, and removal times separated

This report proposes a solution to the open shop scheduling problem with the objective of minimizing total job tardiness in the system. Some practical processing restrictions, such as independent setup and dependent removal times, are taken into account as well. The addressed problem is first described as a 0–1 integer programming model, and is then solved optimally. Subsequently, some hybrid genetic-based heuristics are proposed to solve the problem in an acceptable computation time. To demonstrate the adaptability of these heuristics, some performance comparisons are made with solutions provided by running either a mathematical programming model or certain classic meta-heuristics such as genetic algorithm, simulated annealing, and tabu search in various manufacturing scenarios. The experimental results show that the hybrid genetic-based heuristics perform well, especially the DGA. However, these heuristics require some more additional computations but are still acceptable.     

基于简单特征值问题的修正GEPSVM

针对GEPSVM可能存在奇异性问题,提出一个改进的GEPSVM算法——SMGEPSVM。基于简单特征值问题,得到2个非平行过原点的超平面。与GEPSVM相比,SMGEPSVM不仅可以求解XOR问题,还可求解简单特征值问题,避免GEPSVM奇异性问题,测试精度好于GEPSVM,学习速度更快,其计算结果在人工数据集与UCI上得到了验证。