The Machine Duplication Problem in a Job Shop with Two Jobs

This paper addresses a problem related to the classical job shop scheduling problem with two jobs. The problem consists in concurrently determining the best subset of machines to be duplicated and the optimal scheduling of the operations in order to minimize completion time. Such a problem arises in the tool management for a class of flexible manufacturing cells. The job shop with two jobs is first reviewed, the application of the classical search algorithm A* to this problem is discussed and its performance compared with a previous approach. The complexity of the machine duplication problem is then analysed. The problem is proved to be in general NP-hard in the strong sense, but in a class of special cases, relevant from the applications viewpoint, it can be solved in polynomial time by a dynamic programming algorithm. A heuristic based on such an algorithm and on A* is proposed for the general problem; the results are satisfactory in terms of both efficiency and quality of the solution.     

Constructive heuristics for the Mixed Capacity Arc Routing Problem under Time Restrictions with Intermediate Facilities

The Mixed Capacity Arc Routing Problem under Time Restrictions with Intermediate Facilities (MCARPTIF) is an extension of the Arc Routing Problem under Capacity and Length Restrictions with Intermediate Facilities (CLARPIF) with application in municipal waste collection. This paper evaluates four constructive heuristics capable of computing feasible solutions for the MCARPTIF with a primary objective to either minimise total cost or to minimise the fleet size. The heuristics were adapted from Path-Scanning and Improved-Merge for the Mixed Capacitated Arc Routing Problem, and compared against two Route-First-Cluster-Second heuristics for the MCARPTIF. The objective was to identify the best performing heuristic for application purposes. In practice, the CARP is often solved for real-time or near real-time decision support. Computational time required by the heuristics was thus also evaluated. Identifying the best heuristic proved difficult due to a lack of realistic MCARPTIF benchmark sets, with the two CLARPIF sets predominantly solved in the literature not resembling actual waste collection instances. Route-First-Cluster-Second heuristics, linked with a new vehicle reduction heuristic performed the worst on the two CLARPIF sets, yet performed the best on new waste collection sets taken from the literature and introduced in this paper. Improved-Merge performed the best on two existing CLARPIF sets and on a realistic set with Intermediate-Facilities incident with the vehicle depot, but struggled on all other sets and in minimising fleet size. Path-Scanning was the most robust heuristic, performing reasonably well on all benchmark sets and both objectives. Results further show that due to the high computational time of one of the Route-First-Cluster-Second heuristics, which was only exposed on realistically sized sets, the slightly worse version is the best alternative when real-time support is required for waste collection applications.     

Mathematical programming-based approaches for multi-facility glass container production planning

This paper introduces a mathematical model (together with a relaxed version) and solution approaches for the multi-facility glass container production planning (MF-GCPP) problem. The glass container industry covers the production of glass packaging (bottle and jars), where a glass paste is continuously distributed to a set of parallel molding machines that shape the finished products. Each facility has a set of furnaces where the glass paste is produced in order to meet the demand. Furthermore, final product transfers between facilities are allowed to face demand. The objectives include meeting demand, minimizing inventory investment and transportation costs, as well as maximizing the utilization of the production facilities. A novel mixed integer programming formulation is introduced for MF-GCPP and solution approaches applying heuristics and meta-heuristics based on mathematical programming are developed. A multi-population genetic algorithm defines for each individual the partitions of the search space to be optimized by the MIP solver. A variant of the fix-and-optimize improvement heuristic is also introduced. The computational tests are carried on instances generated from real-world data provided by a glass container company. The results show that the proposed methods return competitive results for smaller instances, comparing to an exact solver method. In larger instances, the proposed methods are able to return high quality solutions.     

Creating Order: The Role of Heuristics in Website Selection

Heuristics, or mental shortcuts, can be efficient tools for decision making; however, they can also lead to biases. This study examines how undergraduate students might use heuristics when evaluating websites retrieved from a Google search. Student participants were asked to review a Google search for “genetically modified food” and select the websites they would likely use for an academic project. The Google search was presented in either the original or reversed order. After indicating initial preferences, students reviewed screen shots of six preselected websites from the Google search and rated each on various content attributes, after which they were asked whether they would use each for their research. The order in which participants saw the results affected their initial choices. Participants were more likely to choose the results near the top of the list. Once students evaluated websites on content attributes, the order effects diminished, but were still detectable. When asked to evaluate the websites, students demonstrated an understanding of what to look for and rated them effectively based on their content.     

机动车辆装载问题的一种混合遗传算法实现*

针对货物装载地和运送目的地均已确定情况下的车辆装载问题,给出了基于遗传算法求解的数学模型,并对基本遗传算法的各个算子针对问题的特点提出了改进方法,同时引入启发式策略,形成了一种混合遗传算法.该算法的特点是各个算子都以提高算法收敛速度和解的最优性为目标,同时种群大小是动态变化的,以求在保证群体多样性的同时加快收敛速度.实验结果表明,该算法对求解此类问题是有效的.     

求解二维装箱问题的强化学习启发式算法

二维带形装箱问题是一个经典的NP-hard的组合优化问题,该问题在实际的生活和工业生产中有着广泛的应用.研究该问题,对企业节约成本、节约资源以及提高生产效率有着重要的意义.提出了一个强化学习求解算法.新颖地使用强化学习为启发式算法提供一个初始的装箱序列,有效地改善启发式冷启动的问题.该强化学习模型能进行自我驱动学习,仅使用启发式计算的解决方案的目标值作为奖励信号来优化网络,使网络能学习到更好的装箱序列.使用简化版的指针网络来解码输出装箱序列,该模型由嵌入层、解码器和注意力机制组成.使用Actor-Critic算法对模型进行训练,提高了模型的效率.在714个标准问题实例和随机生成的400个问题实例上测试提出的算法,实验结果显示：提出的算法能有效地改善启发式冷启动的问题,性能超过当前最优秀的启发式求解算法.     

Modelling a tool switching problem on a single NC-machine

The problem addressed in this paper is a tool switching problem on a single numerically controlled machine. In the first part, the sequence of jobs is given and the tooling aspect is dealt with: the uniform case where all switching times are equal is described, and a model for the general nonuniform case is proposed. This problem is reduced to the problem of finding a minimum cost flow of maximum value in an acyclic network. The second part is devoted to the tool management scheduling problem. Some heuristics are presented and computational results are given and analyzed.     

群体决策支持系统如何解决认知偏误

群体决策支持系统（ＧｒｏｕｐＤｅｃｉｓｉｏｎＳｕｐｐｏｒｔＳｙｓｔｅｍ，简称ＧＤＳＳ）是计算机支持群体协作的主要系统之一。关于ＧＤＳＳ对群体的影响，已取得了较多的研究成果，但是对于群体决策支持系统如何避免人类在决策思维过程中产生各种认知偏误，仍是研究的空白。研究在计算机支持下决策中发生的认知偏误以及ＧＤＳＳ如何避免和减少这些偏误的产生，对于设计成功的ＧＤＳＳ与提高群体决策的质量有非常重要的意义。文章首先提出ＧＤＳＳ对群体影响的研究模型，并以此分析ＧＤＳＳ对群体作用的研究现状，然后着重论述在人类决策思维的各个阶段可能出现的认知偏误，并针对ＧＤＳＳ如何克服这些偏误提出一些建议。     

HARP: A tableau-based theorem prover

This paper presents HARP, a complete, tableau-based theorem prover for first order logic, which is intended to be used both interactively and as an inference engine for Artificial Intelligence applications. Accordingly, HARP's construction is influenced by the design goals of naturalness, efficiency, usefulness in an Artificial Intelligence environment, and modifiability of the control structure by heuristics. To achieve these goals, HARP accepts the entire language of first order logic, i.e. avoids conversion to any kind of normal form, and combines a proof condensation procedure with explicitly represented, declaratively formulated heuristics to construct and communicate its proofs in a format congenial to people. The proof condensation procedure makes proof shorter and more readable by excising redundancies from proof trees. Domain-independent heuristics are formulated to capture efficient and human-like deduction strategies and to rapidly detect certain types of nontheorems. Domain-dependent heuristics can be used to implement specific control regimes, e.g. to efficiently support inheritance. HARP's architecture-and the concomitant ready extensibility of its control structure by declarative heuristic rules-renders it easy to let extralogical information, e.g. semantic and world knowledge, guide the search for proofs and help eliminate irrelevant premisses.     

白车身侧围工位焊接机器人路径优化研究

针对国内汽车企业中白车身焊接机器人作业顺序不合理的问题，采用启发式的节约算法，有效的解决了机器人规划中的最短路问题，实现了机器人路径的优化，并编写了相应的程序，可以有效地进行焊接路径优化。