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

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

来源：评论

学校读者我要写书评

暂无评论

An Adaptative Multi-GPU based Branch-and-Bound. A Case Study: the flow-shop scheduling problem

An Adaptative Multi-GPU based Branch-and-Bound. A Case Study...

引用

14th IEEE International Conference on High Performance Computing and Communications (HPCC) / IEEE 9th International Conference on Embedded Software and Systems (ICESS)

作者： Chakroun, I. Melab, N. Univ Lille 1 CNRS UMR 8022 LIFLINRIA Lille Nord Europe F-59655 Villeneuve Dascq France

ISBN: (纸本)9780769547497

Solving exactly Combinatorial Optimization problems (COPs) using a Branch-and-Bound (B&B) algorithm requires a huge amount of computational resources. Therefore, we recently investigated designing B&B algorithms on top of graphics processing units (GPUs) using a parallel bounding model. The proposed model assumes parallelizing the evaluation of the lower bounds on pools of sub-problems. The results demonstrated that the size of the evaluated pool has a significant impact on the performance of B&B and that it depends strongly on the problem instance being solved. In this paper, we design an adaptative parallel B&B algorithm for solving permutation-based combinatorial optimization problems such as FSP (flow-shop scheduling problem) on GPU accelerators. To do so, we propose a dynamic heuristic for parameter auto-tuning at runtime. Another challenge of this pioneering work 1 is to exploit larger degrees of parallelism by using the combined computational power of multiple GPU devices. The approach has been applied to the permutation flow-shop problem. Extensive experiments have been carried out on well-known FSP benchmarks using an Nvidia Tesla S1070 Computing System equipped with two Tesla T10 GPUs. Compared to a CPU-based execution, accelerations up to x105 are achieved for large problem instances.

关键词： Branch-and-Bound Algorithms Multi-GPU Computing Parallel Bounding flow-shop scheduling problem

来源：评论

学校读者我要写书评

暂无评论

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

A simulated annealing based beam search algorithm for the fl...

引用

5th International Conference on Machine Learning and Cybernetics

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

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

来源：评论

学校读者我要写书评

暂无评论

An effective water wave optimization algorithm with problem-specific knowledge for the distributed assembly blocking flow-shop scheduling problem

引用

KNOWLEDGE-BASED SYSTEMS 2022年 243卷 108471-108471页

作者： Zhao, Fuqing Shao, Dongqu Wang, Ling Xu, Tianpeng Zhu, Ningning Jonrinaldi Lanzhou Univ Technol Sch Comp & Commun Lanzhou 730050 Peoples R China Tsinghua Univ Dept Automat Beijing 10084 Peoples R China Univ Andalas Dept Ind Engn Padang 25163 Indonesia

The distributed assembly blocking flow-shop scheduling problem (DABFSP), which is a promising area in modern supply chains and manufacturing systems, has attracted great attention from researchers and practitioners. However, minimizing the total tardiness in DABFSP has not captured much attention so far. For solving the DABFSP with the total tardiness criterion, a mixed integer linear programming method is utilized to model the problem, wherein the total tardiness during the production process and assembly process are optimized simultaneously. A constructive heuristic (KBNEH) and a water wave optimization algorithm with problem-specific knowledge (KWWO) are presented. KBNEH is designed by combining a new dispatching rule with an insertion-based improvement procedure to obtain solutions with high quality. In KWWO, effective technologies, such as the re-developed destruction-construction operator, four local search methods under the framework of the variable neighborhood search strategy (VNS), the path-relinking method are applied to improve the performance of the algorithm. Comprehensive numerical experiments based on 900 small-scale benchmark instances and 810 large-scale benchmark instances are conducted to evaluate the performance of the presented algorithm. The experimental results obtained by KWWO are 1 to 4 times better than those obtained by the other comparison algorithms, which demonstrate that the effectiveness of KWWO is superior to the compared state-of-the-art algorithms for the considered problem. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Distributed assembly flow-shop scheduling problem Total tardiness Water wave optimization problem-specific knowledge

来源：评论

学校读者我要写书评

暂无评论

Using Chaos-Parallel Evolutionary Programming to solve the flow-shop scheduling problem

Using Chaos-Parallel Evolutionary Programming to solve the F...

引用

3rd World Congress on Intelligent Control and Automation

作者： Liu, XW Pan, YX Gao, HM Xian Univ Technol Xian 710048 Peoples R China

ISBN: (纸本)7312012035

In this paper, the Chaos-Parallel Evolutionary Programming algorithm is presented to solve the flow-shop scheduling problem. At first, the individuals of each sub-population in the parallel evolutionary programming are found out in the search space by use of the ergodicity properties of chaos states, then each sub-population evolves independently and the best individuals are exchanged between them periodically. The simulation results demostrate that the new algorithm is efficient for optimizing large-scale manufacturing process and the better results can be achieved on both the calculating time and optimizing rate.

关键词： chaos evolutionary programming parallel flow-shop scheduling problem

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model

引用

20th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems

作者： Kuo, I-Hong Horng, Shi-Jinn Kao, Tzong-Wann Lin, Tsung-Lieh Fani, Pingzhi Natl Taiwan Univ Sci & Technol Dept Elect Engn Taipei 106 Taiwan Southwest Jiaotong Univ Inst Mobile Commun Chengdu 610031 Peoples R China Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei 106 Taiwan Natl United Univ Dept Elect Engn Miaoli Taiwan Technol & Sci Inst Northern Taiwan Taipei Taiwan

ISBN: (纸本)9783540733225

In this paper, a new hybrid particle swarm optimization model named HPSO that combines random-key (RK) encoding scheme, individual enhancement (IE) scheme, and particle swarm optimization (PSO) is presented and used to solve the flow-shop scheduling problem (FSSP). The objective of FSSP is to find an appropriate sequence of jobs in order to minimize makespan. Makespan means the maximum completion time of a sequence of jobs running on the same machines in flow-shops. By the RK encoding scheme, we can exploit the global search ability of PSO thoroughly. By the IE scheme, we can enhance the local search ability of particles. The experimental results show that the solution quality of FSSP based on the proposed HPSO is far better than those based on CA [1] and NPSO [1], respectively.

关键词： flow-shop scheduling problem particle swarm optimization random-key encoding scheme individual enhancement scheme

来源：评论

学校读者我要写书评

暂无评论

scheduling of Printed Circuit Board Production with Mathematical Solvers 23

Scheduling of Printed Circuit Board Production with Mathemat...

引用

23rd IEEE International Symposium for Design and Technology in Electronic Packaging (SIITME)

作者： Farkas, G. A. Martinek, P. Budapest Univ Technol & Econ Dept Elect Technol Budapest Hungary

ISBN: (纸本)9781538616260

This paper introduces a new approach which supports product plan optimization for PCB manufacturing. The scheduling of the PCB manufacturing line is modelled by the flow shop scheduling problem in our method. The basic aim is to shorten the computational time of the optimization while getting a lower value for the overall makespan. Three different methods are proposed in this paper, which are based on the different initialization of the optimization algorithm. The first contains a heuristic approximation technique pre-optimizing the input data. A starting schedule is provided with a constructive and quick method (i.e. DR (dispatching rule)), before starting the calculation of the actual scheduling. In the next case we focus on tuning the optimization algorithm. Different abilities like search control of the IBM ILOG CPLEX Optimization Studio's FDS (Failure Directed Search) algorithm were examined. Former, valid production plans are used for re-initializing the algorithm run to shorten the required computational time during optimization in another approach described in the paper in details.

关键词： scheduling on PCB manufacturing flow-shop scheduling problem creating production plans lowering scheduling algorithm run-time

来源：评论

学校读者我要写书评

暂无评论

On heuristic approach for solution of scheduling problem involving transportation time and break-down times for three machines

引用

Research Journal of Applied Sciences, Engineering and Technology 2014年第13期7卷 2596-2598页

作者： Khodadadi, A. Department of Statistics Razi University Kermanshah 67149 Iran

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as automated guided vehicles and conveyors and finished jobs are delivered to customers or warehouses by vehicles such as trucks. Most machine scheduling models assume either that there are a finite number of transporters for delivering jobs or that jobs are delivered instantaneously from one location to another without transportation time involved. In this study we study a new simple heuristic algorithm for a '3-machine, n-job' flow shop scheduling problem in which transportation time and break down times of machines are considered. A heuristic approach method to find optimal and near optimal sequence minimizing the total elapsed time. © Maxwell Scientific Organization, 2014.

关键词： Break down time flow-shop scheduling problem Optimal sequence Transportation time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：