检索结果-内蒙古大学图书馆

An improved version of the neh algorithm and its application to large-scale flow-shop scheduling problems

IIE TRANSACTIONS 2007年第2期39卷 229-234页

作者： Jin, Feng Song, Shiji Wu, Cheng Tsing Hua Univ Dept Automat Beijing 100084 Peoples R China

This paper deals with the Flow-shop Scheduling Problem (FSP). The neh algorithm is regarded as one of the best constructive methods for solving the FSP. However, the running time of the neh algorithm when used to solve large-scale FSPs is fairly long. The block properties of the FSP are investigated to reduce the running time. Using these block properties it is found that if a partial schedule is evaluated, the lower bounds of other partial makespans can be obtained in a time of O(1). A pruning procedure based on the block properties of the FSP is introduced into the neh algorithm to reduce the computational complexity. Experimental results show that the improved neh algorithm has a greatly reduced running time compared with the classical neh algorithm. It takes less than 0.2 seconds on average to get a solution for a large-scale FSP (up to 500 jobs and 20 machines).

关键词： flow-shop scheduling problem neh algorithm block property

来源：评论

学校读者我要写书评

暂无评论

Discrete-Event Simulation Integrates an Improved neh algorithm for Practical Flowshop Scheduling Problems in the Satellite Industry

引用

APPLIED SCIENCES-BASEL 2024年第21期14卷 9755页

作者： Li, Guangzhen Zhang, Lei Chang Guang Satellite Technol Co Ltd Changchun 130032 Peoples R China Chinese Acad Sci Changchun Inst Opt Fine Mech & Phys Changchun 130033 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China

The production of multiple types of satellites based on a common manufacturing platform represents a permutation flowshop scheduling problem (PFSP) with complex constraints. This is a highly complex scheduling problem, yet there is still a gap between theoretical research and practical application, particularly in the satellite industry. Therefore, we propose a more practical method that integrates discrete-event simulation modelling and an improved neh algorithm to solve a more realistic PFSP. The discrete-event simulation-based method includes the following three main components: a flexible PFSP simulation modelling approach, an improved neh algorithm, and an interaction mechanism between the simulation model and the optimisation algorithm. The proposed method allows automatic and flexible simulation modelling according to the characteristics of the actual satellite manufacturing workshop, which determines the practical nature of the approach proposed in this paper and then achieves excellent scheduling results based on the special interaction mechanism. The computational results demonstrate that this is a 9.18% improvement over the initial neh algorithm and a 1.40% improvement over the best current improved neh algorithm.

关键词： discrete-event simulation simulation modelling satellite batch production flowshop scheduling neh algorithm Plant Simulation

来源：评论

学校读者我要写书评

暂无评论

Two Techniques to Improve the neh algorithm for Flow-Shop Scheduling Problems

Two Techniques to Improve the NEH Algorithm for Flow-Shop Sc...

引用

7th International Conference on Intelligent Computing (ICIC)

作者： Liu, Gengcheng Song, Shiji Wu, Cheng Tsinghua Univ Dept Automat Beijing 100084 Peoples R China

ISBN: (纸本)9783642259432

Flow-shop scheduling problem (FSP) has been widely investigated in the area of manufacturing systems. Up to now, the neh algorithm is the best heuristic approach to solve FSP. However, in large-scale problems, it takes quite long time for the neh algorithm to find an approximate optimal solution. In this paper, two new techniques are proposed to improve the neh algorithm. Firstly, to reduce the running time, block properties are developed and introduced to neh algorithm. Secondly, to obtain solutions with smaller makespan, tie-break rules are applied. Simulation results show that these two techniques perform well in improving the neh algorithm.

关键词： FSP neh algorithm block property tie-break rule

来源：评论

学校读者我要写书评

暂无评论

A Novel Hybrid Differential Evolutionary algorithm for Solving Multi-objective Distributed Permutation Flow-Shop Scheduling Problem

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS 2025年第1期18卷 1-22页

作者： Du, Xinzhe Zhou, Yanping Qingdao Univ Sci & Technol Sch Informat Sci & Technol Qingdao 266061 Peoples R China

The Distributed Permutation Flow-Shop Scheduling Problem (DPFSP) is a classic issue in distributed scheduling that involves job allocation and processing order within a factory, and it is known to be NP-hard. Numerous researchers have proposed various intelligent optimization algorithms to address the DPFSP;however, there are fewer studies related to the multi-objective DPFSP problem, and the algorithms for solving this problem also suffer from poor solution quality and tend to fall into local optimization and so on. To tackle the multi-objective DPFSP, this paper proposes a novel hybrid differential evolutionary algorithm aimed at minimizing both the maximum completion time and total delay time. In this algorithm, Bernoulli chaotic mapping is applied during the population initialization process to enhance the diversity of the initial population. Additionally, an adaptive mutation factor and crossover rate are designed to balance the global and local search capabilities of the algorithm. Furthermore, a novel selection strategy is constructed based on the neh algorithm, specular reflection learning, and Pareto dominance relation to improve the quality of the solution set when solving instances of varying sizes. This strategy enhances the algorithm's optimization ability and helps it escape local optima. The effectiveness and superiority of the proposed algorithm are verified through 24 instances of different sizes. The results demonstrate that the proposed algorithm outperforms other improved algorithms in terms of convergence, and the uniformity and diversity of the solution set, making it an effective solution for the multi-objective distributed permutation flow-shop scheduling problem.

关键词： Bernoulli chaotic mapping Differential evolutionary Distributed permutation flow-shop scheduling problem Multi-objective optimization neh algorithm Specular reflection learning

来源：评论

学校读者我要写书评

暂无评论

A smart algorithm for multi-criteria optimization of model sequencing problem in assembly lines

引用

ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING 2020年 61卷 101844-000页

作者： Rauf, Mudassar Guan, Zailin Sarfraz, Shoaib Mumtaz, Jabir Shehab, Essam Jahanzaib, Mirza Hanif, Muhammad Huazhong Univ Sci & Technol Sch Mech Sci & Engn State Key Lab Digital Mfg Equipment & Technol Wuhan 430074 Hubei Peoples R China Cranfield Univ Sch Aerosp Transport & Mfg Mfg Dept Cranfield Beds England Nazarbayev Univ Sch Engn Astana Kazakhstan Univ Engn & Technol Taxila Fac Ind Engn Taxila Pakistan Huazhong Univ Sci & Technol Sch Comp Sci Wuhan 430074 Hubei Peoples R China

Assembly Lines (ALs) are used for mass production as they offer lots of advantages over other production systems in terms of lead time and cost. The advent of mass customization has forced the manufacturing industries to update to Mixed-Model Assembly Lines (MMALs) but at the cost of increased complexity. In the real world, industries need to determine the sequence of models based on various conflicting performance measures/criteria. This paper investigates the Multi-Criteria Model Sequencing Problem (MC-MSP) using a modified simulation integrated Smart Multi-Criteria Nawaz, Enscore, and Ham (SMC-neh) algorithm. To address the multiple criteria, a modified simulation integrated Smart Multi-Criteria Nawaz, Enscore, and Ham (SMC-neh) algorithm was developed by integrating a priori approach with neh algorithm. Discrete Event Simulation (DES) was used to evaluate each solution. A mathematical model was developed for three criteria: flow time, makespan and idle time. Further, to validate the effectiveness of the proposed SMC-neh a case study and Taillard's benchmark instances were solved and a Multi-Criteria Decision-Making (MCDM) analysis was performed to compare the performance of the proposed SMC-neh algorithm with the traditional neh algorithm and its variants. The results showed that the proposed SMC-neh algorithm outperformed the others in optimizing the conflicting multi criteria problem.

关键词： Multi-criteria optimization neh algorithm Assembly Lines Mixed-Model Sequencing Smart algorithm

来源：评论

学校读者我要写书评

暂无评论

A new heuristic for the n-job, m-machine flow-shop problem

引用

PRODUCTION PLANNING & CONTROL 2001年第7期12卷 648-653页

作者： Pour, HD Polytech Univ Technol Dept Ind Engn Tehran Iran

This paper describes a new algorithm for solving the flow-shop scheduling problem of n/m/F/F-max to minimize maximum flow time. A set of 2000 randomly produced problems of different sizes was solved and compared with three well-known heuristics. The result reveals that the new algorithm improves the best heuristics in performance measures by a significant percentage. Also, because the number of necessary operations for solving problems in this algorithm is independent of the number of machines involved, it is apt for systems with large numbers of machines. This work helps in solving flow-shop scheduling problems for manufacturing systems with large numbers of machines.

关键词： flow-shop heuristics CDS algorithm neh algorithm Palmer algorithm efficiency index relative error index

来源：评论

学校读者我要写书评

暂无评论

A New Ant algorithmic Approach for Solving PFSP

引用

IRANIAN JOURNAL OF SCIENCE AND TECHNOLOGY TRANSACTION A-SCIENCE 2022年第1期46卷 181-188页

作者： Rad, Shahriar Farahmand Payame Noor Univ Dept Math POB 19395-3697 Tehran Iran

In this paper, a new ant algorithmic approach is presented for solving n-job, m-machine permutation flow shop scheduling problem. The main objective is to find a permutation of n given jobs, i.e., sigma: {1, 2, ... , n} -> {1, 2, ... , n}. This permutation minimizes the maximum completion time of the schedule arising from sigma. An illustration of using the presented heuristic algorithm for finding a good initial sequence of jobs is given. The proposed method is an ant-based approach to permutation flow shop scheduling problem by the behavior of real ants, but it is different with the pheromone trail concept. The presented model is compared against the one by neh which has been considered the best constructive algorithm so far. Regarding the quality of results, the superiority of the proposed method over neh is demonstrated by computational evaluation. The comparison is produced on generated random test problems. This comparison is drawn in domain of feasible instances. It is easy to implement the produced method as a metaheuristic.

关键词： Scheduling Heuristics Permutation flow shop Makespan neh algorithm Initial sequence

来源：评论

学校读者我要写书评

暂无评论

A simulated annealing based beam search algorithm for the flow-shop scheduling problem

引用

INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE 2008年第1期22卷 65-75页

作者： Jin, Feng Song, Shi-Ji Wu, Cheng Tsinghua Univ Dept Automat Beijing 100084 Peoples R China

Beam search algorithm, as an adaptation of branch and bound method, is regarded as one of the effective approaches in solving combinational optimization problems. In this paper, a new beam search algorithm for the large-scale permutation flow shop scheduling problem (FSP) is proposed. A new branching scheme is addressed and compared with the traditional branching scheme. With the new branching scheme, the number of partial schedules in the search tree can be greatly reduced. Based on a simple simulated annealing algorithm, partial schedules are globally evaluated. Numerical experiments show that good solutions of large-scale FSPs could be found with the proposed algorithm in a short time.

关键词： algorithm of beam search flow-shop scheduling problem branching scheme neh algorithm simulated annealing

来源：评论

学校读者我要写书评

暂无评论

Reduction in total completion time in a sequential manufacturing environment 3

Reduction in total completion time in a sequential manufactu...

引用

3rd International Conference on Materials, Manufacturing and Modelling (ICMMM)

作者： Dhanasakkaravarthi, B. Krishnamoorthy, A. Sathyabama Inst Sci & Technol Chennai 600119 Tamil Nadu India Mech Engn Chennai 600005 Tamil Nadu India

In any manufacturing environment, the materials are to be processed to the required geometry using different processes. The processes usually indicate the actions to be completed in a set of machines. Among the processes, some may have to follow a sequence means, after completing a particular process only we can move to the other one. In such cases, permutation flowshop layouts are preferred over other layouts. Out of several parameters, minimization of makespan has been studied much over the years by many researchers. The problems are widely regarded as NP-hard if the number of machines is more than three. As the computation time grows exponentially with the problem size, heuristics with acceptable level of accuracies have been proposed by many authors. The neh algorithm proposed in 1983 is still considered as one of the best simple, constructive heuristics for the minimization of makespan. This paper proposes a simple tie-breaking rule to reduce the total completion time (makespan) further without increasing the time complexity. The concept of Slope Indices is used for this purpose. The computation results using the Taillard test bed indicate improvement up to 5.85% over the reference neh algorithm. (c) 2021 Elsevier Ltd. All rights reserved. Selection and peer-review under responsibility of the scientific committee of the 3rd International Conference on Materials, Manufacturing and Modelling.

关键词： Flowshop scheduling Heuristic neh algorithm Slope indices Makespan

来源：评论

学校读者我要写书评

暂无评论

A new beam search algorithm for the large-scale permutation FSP

A new beam search algorithm for the large-scale permutation ...

引用

5th International Conference on Machine Learning and Cybernetics

作者： Jin, Feng Song, Shi-Ji Wu, Cheng Tsinghua Univ Dept Automat Beijing 100084 Peoples R China

ISBN: (纸本)1424400600

Beam Search algorithm, as an adaptation of branch and bound method, is regarded as one of the effective approaches in solving combinational optimization problems. In this paper, a new beam search algorithm for the large-scale permutation flow shop problem is proposed. A new branching scheme is addressed and compared with the traditional branching scheme. With the new branching scheme, the number of partial schedules in search tree can be greatly reduced. To balance the computational effort and solution quality, partial schedules are evaluated with a new approximate function based on forecast. Numerical experiments show that good solutions of large-scale FSPs could be found in a short time with the proposed algorithm.

关键词： beam search algorithm flow shop scheduling problem branching scheme neh algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：