Multiprocessor Task Assignment with Fuzzy Hopfield Neural Network Clustering Technique

Most scheduling applications have been demonstrated as NP-complete problems. A variety of schemes are introduced in solving those scheduling applications, such as linear programming, neural networks, and fuzzy logic. In this paper, a new approach of first analogising a scheduling problem to a clustering problem and then using a fuzzy Hopfield neural network clustering technique to solve the scheduling problem is proposed. This fuzzy Hopfield neural network algorithm integrates fuzzy c-means clustering strategies into a Hopfield neural network. This investigation utilises this new approach to demonstrate the feasibility of resolving a multiprocessor scheduling problem with no process migration and constrained times (execution time and deadline). Each process is regarded as a data sample, and every processor is taken as a cluster. Simulation results illustrate that imposing the fuzzy Hopfield neural network onto the proposed energy function provides an appropriate approach to solving this class of scheduling problem.       

Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling

The expanded job-shop scheduling problem (EJSSP) is a practical production scheduling problem with processing constraints that are more restrictive and a scheduling objective that is more general than those of the standard job-shop scheduling problem (JSSP). A hybrid approach involving neural networks and genetic algorithm (GA) is presented to solve the problem in this paper. The GA is used for optimization of sequence and a neural network (NN) is used for optimization of operation start times with a fixed sequence.

After detailed analysis of an expanded job shop, new types of neurons are defined to construct a constraint neural network (CNN). The neurons can represent processing restrictions and resolve constraint conflicts. CNN with a gradient search algorithm, gradient CNN in short, is applied to the optimization of operation start times with a fixed processing sequence. It is shown that CNN is a general framework representing scheduling problems and gradient CNN can work in parallel for optimization of operation start times of the expanded job shop.

Combining gradient CNN with a GA for sequence optimization, a hybrid approach is put forward. The approach has been tested by a large number of simulation cases and practical applications. It has been shown that the hybrid approach is powerful for complex EJSSP.     

柔性作业车间调度问题的集成启发式算法

柔性作业车间调度问题,包括路径分配和加工排序2大子问题,是组合优化理论和实际生产管理的重要研究方向。作为传统作业车间调度的扩展,柔性作业车间调度问题的内在复杂性(强NP-Hard)使得传统的最优化方法难以有效求解。文章针对以多目标权重和最优为目标的柔性作业车间调度问题,提出基于过滤定向搜索的集成启发式算法,设计改进了节点分枝策略和局部/全局评价函数,能同时解决2大子问题。通过实例仿真,对算法性能进行比较分析和评价,结果表明了算法的可行性和有效性。     

Warm start by Hopfield neural networks for interior point methods

Hopfield neural networks and interior point methods are used in an integrated way to solve linear optimization problems. The Hopfield network gives warm start for the primal–dual interior point methods, which can be way ahead in the path to optimality. The approaches were applied to a set of real world linear programming problems. The integrated approaches provide promising results, indicating that there may be a place for neural networks in the “real game” of optimization.     

基于Hopfield神经网络的作业车间生产调度方法

该文提出了基于Hopfield神经网络的作业车间生产调度的新方法.文中给出了作业车 间生产调度问题(JSP)的约束条件及其换位矩阵表示,提出了新的包括所有约束条件的计算能 量函数表达式,得到相应的作业车间调度问题的Hopfield神经网络结构与权值解析表达式,并 提出相应的Hopfield神经网络作业车间调度方法.为了避免Hopfield神经网络容易收敛到局部 极小,从而产生非法调度解的缺点,将模拟退火算法应用于Hopfield神经网络求解,使Hopfield 神经网络收敛到计算能量函数的最小值0,从而保证神经网络输出是一个可行调度方案.该文 改进了已有文献中提出的作业调度问题的Hopfield神经网络方法,与已有算法相比,能够保证 神经网络稳态输出为可行的作业车间调度方案.     

An improved constraint satisfaction adaptive neural network for job-shop scheduling

This paper presents an improved constraint satisfaction adaptive neural network for job-shop scheduling problems. The neural network is constructed based on the constraint conditions of a job-shop scheduling problem. Its structure and neuron connections can change adaptively according to the real-time constraint satisfaction situations that arise during the solving process. Several heuristics are also integrated within the neural network to enhance its convergence, accelerate its convergence, and improve the quality of the solutions produced. An experimental study based on a set of benchmark job-shop scheduling problems shows that the improved constraint satisfaction adaptive neural network outperforms the original constraint satisfaction adaptive neural network in terms of computational time and the quality of schedules it produces. The neural network approach is also experimentally validated to outperform three classical heuristic algorithms that are widely used as the basis of many state-of-the-art scheduling systems. Hence, it may also be used to construct advanced job-shop scheduling systems.     

Constraint satisfaction adaptive neural network and heuristicscombined approaches for generalized job-shop scheduling

This paper presents a constraint satisfaction adaptive neural network, together with several heuristics, to solve the generalized job-shop scheduling problem, one of NP-complete constraint satisfaction problems. The proposed neural network can be easily constructed and can adaptively adjust its weights of connections and biases of units based on the sequence and resource constraints of the job-shop scheduling problem during its processing. Several heuristics that can be combined with the neural network are also presented. In the combined approaches, the neural network is used to obtain feasible solutions, the heuristic algorithms are used to improve the performance of the neural network and the quality of the obtained solutions. Simulations have shown that the proposed neural network and its combined approaches are efficient with respect to the quality of solutions and the solving speed.     

改进计算能量函数下作业车间调度的混沌神经网络方法

神经网络是求解作业车间调度问题的一种有效方法,本文研究可以获得全局最优或近似全局最优的可行解的作业车问调度神经网络方法.给出包括作业车间调度所有约束条件的新的计算能量函数表达式,并把混沌动力学应用于离散Hopfield神经网络作业车间调度中,提出一种改进的暂态混沌离散神经网络作业车间调度方法.仿真结果表明,该方法不仅具有全局搜索能力,而且收敛速度较快,重要的是能够保证神经网络的稳态输出为全局最优或近似全局最优的可行的作业车间调度方案.     

Machine grouping using sequence-based similarity coefficients and neural networks

Most neural network approaches to the cell formation problem do not use information on the sequence of operations on part types. They only use as input the binary part-machine incidence matrix. In this paper we investigate two sequence-based neural network approaches for cell formation. The objective function considered is the minimization of transportation costs (including both intracellular and intercellular movements). Constraints on the minimum and maximum number of machines per cell can be imposed. The problem is formulated mathematically and shown to be equivalent to a quadratic programming integer program that uses symmetric, sequence-based similarity coefficients between each pair of machines. Of the two energy-based neural network approaches investigated, namely Hopfield model and Potts Mean Field Annealing, the latter seems to give better and faster solutions, although not as good as a Tabu Search algorithm used for benchmarking.     

An object-oriented approach for multi-objective flexible job-shop scheduling problem

Flexible manufacturing systems are very complex to control and it is difficult to generate controlling systems for this problem domain. Flexible job-shop scheduling problem (FJSP) is one of the instances in this domain. It is a problem which inherits the job-shop scheduling problem (JSP) characteristics. FJSP has additional routing sub-problem in addition to JSP. In routing sub-problem each operation is assigned to a machine out of a set of capable machines. In scheduling sub-problem the sequence of assigned operations is obtained while optimizing the objective function(s). In this paper an object-oriented (OO) approach is presented for multi-objective FJSP along with simulated annealing optimization algorithm. Solution approaches in the literature generally use two-string encoding scheme to represent this problem. However, OO analysis, design and programming methodology help to present this problem on a single encoding scheme effectively which result in a practical integration of the problem solution to manufacturing control systems where OO paradigm is frequently used. OO design of FJSP is achieved by using UML class diagram and this design reduces the problem encoding to a single data structure where operation object of FJSP could hold its data about alternative machines in its own data structure hierarchically. Many-to-many associations between operations and machines are transformed into two one-to-many associations by inserting a new class between them. Minimization of the following three objective functions are considered in this paper: maximum completion time, workload of the most loaded machine and total workload of all machines. Some benchmark sets are run in order to show the effectiveness of the proposed approach. It is proved that using OO approach for multi-objective FJSP contributes to not only building effective manufacturing control systems but also achieving effective solutions.     

Design of ANN Based Non-Linear Network Using Interconnection of Parallel Processor

Suspicious mass traffic constantly evolves, making network behaviour tracing and structure more complex. Neural networks yield promising results by considering a sufficient number of processing elements with strong interconnections between them. They offer efficient computational Hopfield neural networks models and optimization constraints used by undergoing a good amount of parallelism to yield optimal results. Artificial neural network (ANN) offers optimal solutions in classifying and clustering the various reels of data, and the results obtained purely depend on identifying a problem. In this research work, the design of optimized applications is presented in an organized manner. In addition, this research work examines theoretical approaches to achieving optimized results using ANN. It mainly focuses on designing rules. The optimizing design approach of neural networks analyzes the internal process of the neural networks. Practices in developing the network are based on the interconnections among the hidden nodes and their learning parameters. The methodology is proven best for nonlinear resource allocation problems with a suitable design and complex issues. The ANN proposed here considers more or less 46k nodes hidden inside 49 million connections employed on full-fledged parallel processors. The proposed ANN offered optimal results in real-world application problems, and the results were obtained using MATLAB.     

Solving large scale combinatorial optimisation problems based on a divide and conquer strategy

A Hopfield neural network for a large scale problem optimisation poses difficulties due to the issues of stability and the determination of network parameters. In this paper, we introduce the concept of a divide and conquer algorithm to solve large scale optimisation problems using the Hopfield neural network. This paper also introduces the Grossberg Regularity Detector (GRD) neural network as a partition tool. This neural network based partition tool has the advantages of reducing the complexity of partition selection as well as removing the recursive division process during the divide and conquer operation. A large scale combinatorial optimisation problem (i.e. sequence-dependent set-up time minimisation problem with a large number of parts (N> 100)) is linearly partitioned into smaller sets of sub-problems based on their similarity relations. With a large number of parts (N>100), the problem could not effectively be verified with other methods, such as the heuristic or branch and bound methods. Hence, the effectiveness of the divide and conquer strategy implemented by the GRD neural network in conjunction with a Hopfield neural network was benchmarked against the first-come first-serve method, and the Hopfield neural network based on arbitrary separations. The results showed that the divide and conquer strategy of the GRD neural network was far superior to the other methods.     

Mathematical modeling and a hybridized bacterial foraging optimization algorithm for the flexible job-shop scheduling problem with sequencing flexibility

The flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem (JSP) in which operations can be performed by a set of candidate capable machines. An extended version of the FJSP, entitled sequencing flexibility, is studied in this work, which considers precedence between the operations in the form of a directed acyclic graph instead of a sequential order. In this work, a mixed integer linear programming (MILP) formulation is presented to minimize weighted tardiness for the FJSP with sequencing flexibility. Due to the NP-hardness of the problem, a novel biomimicry hybrid bacterial foraging optimization algorithm (HBFOA) is developed, which is inspired by the behavior of E. coli bacteria in its search for food. The developed HBFOA search method is hybridized with simulated annealing (SA). Additionally, the algorithm has been enhanced by a local search method based on the manipulation of critical operations. Classical dispatching rules have been employed to create the initial swarm of HBFOA, and a new dispatching rule named minimum number of operations has been devised. The developed approach has been packaged in the form of a decision support system (DSS) developed on top of Microsoft Excel—a tool most small and mid-range enterprises (SME) use heavily for planning. A case study with local industry is presented to validate the proposed HBFOA and MILP. Additional numerical experiments using literature benchmarks are further used for validation. The results demonstrate that the HBFOA outperformed the classical dispatching rules and the best integer solution of MILP when minimizing the weighted tardiness and offered comparable results for the makespan instances.     

A Discrete-Time Quantized-State Hopfield Neural Network

A discrete-time quantized-state Hopfield neural network is analyzed with special emphasis in its convergence, complexity and scalability properties. This network can be considered as a generalization of the Hopfield neural network by Shrivastava et al. [27] into the interior of the unit hypercube. This extension allows its use in a larger set of combinatorial optimization problems and its properties make of it a good candidate to build hybrid algorithms along with other heuristics such as the evolutive algorithms. Finally, the network is illustrated in some instances of the linear assignment problem and the frequency assignment problem.     

基于改进能量函数的混沌神经网络JSP解法

针对传统Hopfield神经网络(HNN)在求NP类问题的解时易陷入局部最优点的不足,提出基于改进能量函数的模拟退火混沌神经网络算法。通过在Hopfield神经网络中引入混沌机制,并结合退火策略控制混沌动态,有效避免了陷入局部极小的缺陷,因此将其用于求解JSP（作业车间调度）。算法改进了表示JSP的换位矩阵,给出了包含目标函数的能量函数,保证了网络的稳态输出为全局可行解。     

基于神经网络的图象序列特征点匹配

利用神经网络优化技术解决图象序列的特征点匹配问题，将特征点匹配归结为一个带约束的优化问题，并用2D Hopfield网络实现，在Hopfield网络的能量函数的设计中，综合考虑了特征点的预测结果、特征点的遮挡等情况，从而克服了现有的多数方法所存在的误匹配现象，对于特征点的跟踪，头3帧图象的正确匹配是十分关键的。本文提出了一种3D Hopfield网络用以解决头3帧图象的特征点匹配，并提出了一个运动平滑性的代价函数用以构造3D Hopfield网络的能量函数，实际图象序列的实验结果证明了本方法的有效性。     

基于神经网络求解三值模型下的故障诊断问题

在多处理机系统的系统级故障诊断中,一个重要的研究课题是确定最可能故障处理机集,该问题可以归结为NP一完全的整数线性规划问题。连续Hopfietd神经网络能够近似求解最优化问题,因此是解决这类问题的可选路径。文中主要研究如何构建连续Hopfield神经网络,以在三值PMC模型下近似地确定最可能故障集,相比于常用的二值诊断模型,能得到更准确的诊断结果。在超立方体结构上进行了一系列的数值实验,仿真结果表明：该方法具有实用性。     

基于神经网络模型的有约束的FMS资源调度

本文介绍了用神经网络求解ＦＭＳ中有约束的资源调度问题的方法，有约束的资源调度问题首和无被分解成一系列多维背包模型并且为背包模型建立了一个等价的Ｈｏｐｆｉｅｌｄ神经网络，然后通过扩展Ｈｏｐｆｉｅｌｄ网络，给出了一种求解有约束的资源调度问题的方法。这咱方法可以避免通常神经网络所具有的不稳定性和容易陷入局部极小点的缺陷。     

Implementing heuristics as an optimization criterion in neural networks for job-shop scheduling

Recently neural network architectures have been developed that are capable of solving deterministic job-shop scheduling problems, part of the large class of NP-complete problems. In these architectures, however, no valid optimization criterion has been implemented. In this paper an enhanced neural network architecture for job-shop scheduling is proposed in which general rules of thumb for job-shop scheduling have been incorporated as a local optimization criterion. Implementation of the rules of thumb, by adaptation of the network architecture, results in a network that actually incorporates the optimization criterion, enabling parallel hardware implementation. Owing to the implemented local optimization criterion the performance of the network architecture is superior to previously presented architectures. Comparison with advanced heuristic sequential schedulers showed equal performance with respect to the quality of the solutions and better performance with respect to calculation speed.