An efficient heuristic for scheduling batches of parts in a flexible flow system

Flexible manufacturing systems (FMSs) are a class of automated systems that can be used to improve productivity in batch manufacturing. Four stages of decision making have been defined for an FMS—the design, planning, scheduling, and control stages. This research focuses on the planning stage, and specifically in the area of scheduling batches of parts through the system.The literature to date on the FMS planning stage has mostly focused on the machine grouping, tool loading, and parttype selection problems. Our research carries the literature a step further by addressing the problem of scheduling batches of parts. Due to the use of serial-access material-handling systems in many FMSs, the batch-scheduling problem is modeled for a flexible flow system (FFS). This model explicitly accounts for setup times between batches that are dependent on their processing sequence.A heuristic procedure is developed for this batch-scheduling problem—the Maximum Savings (MS) heuristic. The MS heuristic is based upon the savings in time associated with a particular sequence and selecting the one with the maximum savings. It uses a two-phase method, with the savings being calculated in phase I, while a branch-and-bound procedure is employed to seek the best heuristic solution in phase II. Extensive computational results are provided for a wide variety of problems. The results show that the MS heuristic provides good-quality solutions.     

Minimizing the number of tool switches on a flexible machine

This article analyzes a tool switching problem arising in certain flexible manufacturing environments. A batch of jobs have to be successively processed on a single flexible machine. Each job requires a subset of tools, which have to be placed in the tool magazine of the machine before the job can be processed. The tool magazine has a limited capacity, and, in general, the number of tools needed to produce all the jobs exceeds this capacity. Hence, it is sometimes necessary to change tools between two jobs in a sequence. The problem is then to determine a job sequence and an associated sequence of loadings for the tool magazine, such that the total number of tool switches is minimized. This problem has been previously considered by several authors; it is here revisited, both from a theoretical and from a computational viewpoint. Basic results concerning the computational complexity of the problem are established. Several heuristics are proposed for its solution, and their performance is computationally assessed.     

An expert decision support system for network routing: a case study

The paper presents a case study of the development of an expert decision support system which uses simple heuristic methods for fast determination of routes for simultaneous signals in a transmission network of limited capacity. It illustrates how heuristic solutions can be embodied in a model-based DSS and how the standard decision support literature, although intuitively appealing, provides little practical assistance in system construction or classification     

Adaptive flexibility and maladaptive routines in selecting fast and frugal decision strategies.

Decision routines unburden the cognitive capacity of the decision maker. In changing environments, however, routines may become maladaptive. In 2 experiments with a hypothetical stock market game (n = 241), the authors tested whether decision routines tend to persist at the level of decision strategies rather than at the level of options in strategy selection. The payoff structure of the task was changed after 80 decision trials, rendering a new strategy optimal with respect to expected payoff. Whereas most participants detected the appropriate strategy at the beginning of the task, they tended to retain it even when it was no longer optimal. A hint about a possible change had only a small influence on this maladaptive routine; a monetary incentive had none. Switching to a similar but not identical task relaxed the routine, but not much. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Incorporating statistical information into expert classification systems to reduce classification costs

Interactive expert systems seek relevant information from a user in order to answer a query or to solve a problem that the user has posed. A fundamental design issue for such a system is therefore itsinformation-seeking strategy, which determines the order in which it asks questions or performs experiments to gain the information that it needs to respond to the user. This paper examines the problem of optimal knowledge acquisition through questioning in contexts where it is expensive or time-consuming to obtain the answers to questions. An abstract model of an expert classification system — considered as a set of logical classification rules supplemented by some statistical knowledge about attribute frequencies — is developed and applied to analyze the complexity and to present constructive algorithms for doing probabilistic question-based classification. New heuristics are presented that generalize previous results for optimal identification keys and questionnaires. For an important class of discrete discriminant analysis problems, these heuristics find optimal or near-optimal questioning strategies in a small fraction of the time required by an exact solution algorithm.     

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

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

唐家山堰塞湖泄洪问题几种模型探讨

以唐家山堰塞湖为研究对象,首先根据当时权威新闻报道数据及数字高程模型用数值积分和拟合两种方法求堰塞湖的蓄水量。在溃坝阶段,由经验公式及进出水量平衡建立模型,从而拟合出溃口的深度和宽度随时间变化的表达式。在泛洪阶段,采用静态分析,假设水流呈圆形蔓延采用先离散后整合叠加的方法建立柱体模型得到被淹面积和淹没深度,并在此基础上考虑洪水淹没区域中人口密集区域的人员撤离方案。     

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

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

课程表问题的一种模拟退火超启发式算法

课程表问题是经典的组合优化问题,属于NP-hard问题.长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法.在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法.在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法.与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排.旅行商问题、背包问题等应用领域.实验表明,该算法是可行有效的,且无一例时间、空间冲突.     

动态搜索算法求解时间依赖型旅行商问题研究

时间依赖型旅行商问题(TDTSP)是旅行商问题(TSP)的延伸.在该问题中,任意两节点间的旅行时间(成本)不仅取决于节点间的距离,还依赖于一天中具体时段或节点在哈密顿圈中所处的具体位置.对基于节点所处哈密顿圈中具体位置的TDTSP问题建立相应的数学模型,并提出求解该问题的动态搜索算法.通过实验仿真,验证了动态搜索算法优于目前在邻域搜索领域求解该问题最有效的动态规划启发式算法.