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

Logic-based Benders decomposition methods for the distributed permutation flow shop scheduling problem with production and transportation cost

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 179卷

作者： Xiong, Fuli Shi, Jiangbo Jing, Lin Ping, An Xian Univ Architecture & Technol Sch Informat & Control Engn Xian 710055 Peoples R China

Distributed manufacturing mode can significantly enhance production flexibility and efficiency. Considering that factories and customers in distributed manufacturing environments may be geographically dispersed, address a distributed permutation flow shop scheduling problem (DPFSP) with direct transportation different cost of production and transportation while the goal is to minimize of weighted sum cost makespan (DPFSP-PTM). First, we formulate two mixed-integer linear programming (MILP) models and constraint programming (CP) model to optimize the objective simultaneously. Then, by decomposing DPFSPPTM into an order assignment master problem (AMP) and a series of scheduling subproblems (SSPs), develop two exact methods based on logic-based Benders decomposition (LBBD) and Branch-and-Check (BCH). To accelerate convergence, we propose three strong SSP relaxations based on the single-machine bottleneck enhance the MILP models and AMP. Additionally, we introduce an initial solution generated by the iterated greedy (IG) algorithm to warm-start the LBBD. Finally, we demonstrate the effectiveness of the proposed methods in achieving competitive average optimality gaps and lower bounds across both small-scale large-scale instances.

关键词： Distributed permutation flow shop scheduling problem Logic-based Benders decomposition Branch-and-Check Mixed-integer linear programming Constraint programming iterated greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Developing algorithm and dispatching rules for scheduling a realistic flexible flow shop with setups to minimize total weighted tardiness

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2025年第1期138卷 225-245页

作者： Hsieh, Feng Yu Lin, Yang Kuei Wang, Yi-Chi Feng Chia Univ Dept Ind Engn & Syst Management Taichung 407 Taiwan

In this research, we are studying the scheduling problem of a professional ball manufacturing company in Taiwan. The problem is related to scheduling a flexible flow shop that includes setups with the aim of minimizing total weighted tardiness. We first present a mathematical model for the studied problem. Next, we conduct data processing and generate initial solutions. This involves extracting ordering data from the company, aggregating the total demand based on the product types of all orders, and splitting the demand into sublots. For production purposes, each subplot will be matched with a production lot, abbreviated as PLot. We assign a score to each order based on customer priority, order amount, due date, and order profitability. This has allowed us to propose a strategy in which orders compete for production priority based on their scores. We also proposed four dispatching rules to assign PLots to machines based on their production priority. Finally, we have suggested an iterated greedy algorithm with mutation (IGm algorithm) to improve the initial solutions obtained through dispatching rules. Extensive computational runs based on real data have been conducted to compare the performances of the proposed orders competing for production priority, the four dispatching rules, and the IGm algorithm with sequences generated by the EDD (Earliest Due Date) and WEDD (Weighted Earliest Due Date) rules. Computational results demonstrate that the proposed orders competing for production priority, along with the dispatching rules and the IGm algorithm, are effective in providing promising results for the scheduling problem.

关键词： Scheduling Flexible flow shop Steel ball Dispatching rules iterated greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimization of makespan for the distributed no-wait flow shop scheduling problem with iterated greedy algorithms

引用

KNOWLEDGE-BASED SYSTEMS 2017年第Dec.1期137卷 163-181页

作者： Shao, Weishi Pi, Dechang Shao, Zhongshi Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing Jiangsu Peoples R China Collaborat Innovat Ctr Novel Software Technol & I Nanjing Jiangsu Peoples R China 169 Sheng Tai West Rd Nanjing Jiangsu Peoples R China

The distributed production lines widely exist in modern supply chains and manufacturing systems. This paper aims to address the distributed no-wait flow shop scheduling problem (DNWFSP) with the makespan criterion by using proposed iterated greedy (IG) algorithms. Firstly, several speed-up methods based on the problem properties of DNWFSP are investigated to reduce the evaluation time of neigh-borhood with O(1) complexity. Secondly, an improved NEH heuristic is proposed to generate a promising initial solution, where the iteration step of the insertion step of NEH is applied to the factory after inserting a new job. Thirdly, four neighborhood structures (i.e. Critical_swap_single, Critical_insert_single, Critical_swap_multi, Critical_insert_multi) based on factory assignment and job sequence adjustment are employed to escape from local optima. Fourthly, four local search methods based on neighborhood moves are proposed to enhance local searching ability, which contains LS_insert_critical_factory1, LS_insert_critical_factory2, LS_swap, and LS_insert. Finally, to organize neighborhood moves and local search methods efficiently, we incorporate them into the framework of variable neighborhood search (VNS), variable neighborhood descent (VND) and random neighborhood structure (RNS). Furthermore, three variants of IG algorithms are presented based on the designed VNS, VND and RNS. The parameters of the proposed IG algorithms are tuned through a design of experiments on randomly generated benchmark instances. The effectiveness of the initialize phase and local search methods is shown by numerical comparison, and the comparisons with the recently published algorithms demonstrate the high effectiveness and searching ability of the proposed IG algorithms for solving the DNWFSP. Ultimately, the best solutions of 720 instances from the well-known benchmark set of Naderi and Ruiz for the DNWFSP are proposed. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Distributed no-wait flow shop scheduling problem Makespan iterated greedy algorithm Neighborhood structures Local search

来源：评论

学校读者我要写书评

暂无评论

Finding the minimum k-weighted dominating sets using heuristic algorithms

引用

Mathematics and Computers in Simulation 2025年 228卷 485-497页

作者： Barrena, E. Bermudo, S. Hernández-Díaz, A.G. López-Sánchez, A.D. Zamudio, J.A. Department of Economics Quantitative Methods Economic History. Universidad Pablo de Olavide ES-41013 Seville Spain CISPA Helmholtz Center for Information Security Saarbrücken Germany

In this work, we propose, analyze, and solve a generalization of the k-dominating set problem in a graph, when we consider a weighted graph. Given a graph with weights in its edges, a set of vertices is a k-weighted dominating set if for every vertex outside the set, the sum of the weights from it to its adjacent vertices in the set is bigger than or equal to k. The k-weighted domination number is the minimum cardinality among all k-weighted dominating sets. Since the problem of finding the k-weighted domination number is NP-hard, we have proposed several problem-adapted construction and reconstruction techniques and embedded them in an iterated greedy algorithm. The resulting sixteen variants of the iterated greedy algorithm have been compared with an exact algorithm. Computational results show that the proposal is able to find optimal or near-optimal solutions within a short computational time. To the best of our knowledge, the k-weighted dominating set problem has never been studied before in the literature and, therefore, there is no other state-of-the-art algorithm to solve it. We have also included a comparison with a particular case of our problem, the minimum dominating set problem and, on average, we achieve same quality results within around 50% of computation time. © 2024 The Authors

关键词： Edge-weight Dominating set Metaheuristic algorithm iterated greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

iterated-greedy-based algorithms with beam search initialization for the permutation flowshop to minimise total tardiness

引用

EXPERT SYSTEMS WITH APPLICATIONS 2018年 94卷 58-69页

作者： Fernandez-Viagas, Victor Valente, Jorge M. S. Framinan, Jose M. Univ Seville Sch Engn Ind Management Camino Descubrimientos S-N Seville 41092 Spain Univ Porto LIAAD INESC TEC Fac Econ Oporto Portugal

The permutation flow shop scheduling problem is one of the most studied operations research related problems. Literally, hundreds of exact and approximate algorithms have been proposed to optimise several objective functions. In this paper we address the total tardiness criterion, which is aimed towards the satisfaction of customers in a make-to-order scenario. Although several approximate algorithms have been proposed for this problem in the literature, recent contributions for related problems suggest that there is room for improving the current available algorithms. Thus, our contribution is twofold: First, we propose a fast beam-search-based constructive heuristic that estimates the quality of partial sequences without a complete evaluation of their objective function. Second, using this constructive heuristic as initial solution, eight variations of an iterated-greedy-based algorithm are proposed. A comprehensive computational evaluation is performed to establish the efficiency of our proposals against the existing heuristics and metaheuristics for the problem. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Scheduling Flowshop Heuristics PFSP Tardiness Beam search iterated greedy algorithm iterated local search

来源：评论

学校读者我要写书评

暂无评论

A Penalty Groups-Assisted iterated greedy Integrating Idle Time Insertion:Solving the Hybrid Flow Shop Group Scheduling with Delivery Time Windows

引用

Complex System Modeling and Simulation 2024年第2期4卷 137-165页

作者： Qianhui Ji Yuyan Han Yuting Wang Biao Zhang Kaizhou Gao the School of Computer Science Liaocheng UniversityLiaocheng 252059China Institute of Systems Engineering Macao University of Science and TechnologyMacao 999078China

The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production ***,there are several unresolved challenges in problem modeling and algorithmic design tailored for *** our study,we place emphasis on the constraint of ***,this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness(TWET).Then a penalty groups-assisted iterated greedy integrating idle time insertion(PG IG ITI)is proposed to solve the above *** the PG IG ITI,a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET ***,to reduce the amount of computation,a skip-based destruction and reconstruction strategy is designed,and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups,i.e.,early and tardy ***,through comprehensive statistical experiments on 270 test instances,the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.

关键词： hybrid flow shop group scheduling iterated greedy algorithm delivery time windows sequence-dependent setup time

来源：评论

学校读者我要写书评

暂无评论

An effective iterated greedy method for the distributed permutation fl owshop scheduling problem with sequence-dependent setup times

引用

SWARM AND EVOLUTIONARY COMPUTATION 2020年 59卷

作者： Huang, Jiang-Ping Pan, Quan-Ke Gao, Liang Shanghai Univ Sch Mechatron Engn & Automat Shanghai 200072 Peoples R China Liaocheng Univ Sch Comp Sci Liaocheng 252000 Shandong Peoples R China Huazhong Univ Sci & Technol State Key Lab Digital Mfg Equipment & Technol Wuhan 430074 Peoples R China

The distributed permutation flowshop scheduling problem (DPFSP) has attracted much attention in recent years. In this paper, we extend the DPFSP by considering the sequence-dependent setup time (SDST), and present a mathematical model and an iterated greedy algorithm with a restart scheme (IGR). In the IGR, we discard the simulated annealing-like acceptance criterion commonly used in traditional iterated greedy algorithms. A restart scheme with six different operators is proposed to ensure the diversity of the solutions and help the algorithm to escape from local optimizations. Furthermore, to achieve a balance between the exploitation and exploration, we introduce an algorithmic control parameter in the IG stage. Additionally, to further improve the performance of the algorithm, we propose two local search methods based on a job block which is built in the evolution process. A detailed design experiment is carried out to calibrate the parameters for the presented IGR algorithm. The IGR is assessed through comparing with the state-of-the-art algorithms in the literature. The experimental results show that the proposed IGR algorithm is the best-performing one among all the algorithms in comparison.

关键词： Flowshop Scheduling iterated greedy algorithm Meta-heuristics

来源：评论

学校读者我要写书评

暂无评论

Dual-Objective Mixed Integer Linear Program and Memetic algorithm for an Industrial Group Scheduling Problem

引用

IEEE/CAA Journal of Automatica Sinica 2021年第6期8卷 1199-1209页

作者： Ziyan Zhao Shixin Liu MengChu Zhou Abdullah Abusorrah State Key Laboratory of Synthetical Automation for Process Industries and the College of Information Science and Engineering Northeastern UniversityShenyang 110819China Department of Electrical and Computer Engineering New Jersey Institute of TechnologyNewark NJ 07102 USA Center of Research Excellence in Renewable Energy and Power Systems King Abdulaziz UniversityJeddah 21481Saudi Arabia Department of Electrical and Computer Engineering Faculty of Engineeringand Center of Research Excellence in Renewable Energy and Power SystemsKing Abdulaziz UniversityJeddah 21481Saudi Arabia

Group scheduling problems have attracted much attention owing to their many practical *** work proposes a new bi-objective serial-batch group scheduling problem considering the constraints of sequence-dependent setup time,release time,and due *** is originated from an important industrial process,i.e.,wire rod and bar rolling process in steel production *** objective functions,i.e.,the number of late jobs and total setup time,are minimized.A mixed integer linear program is established to describe the *** obtain its Pareto solutions,we present a memetic algorithm that integrates a population-based nondominated sorting genetic algorithm II and two single-solution-based improvement methods,i.e.,an insertion-based local search and an iterated greedy *** computational results on extensive industrial data with the scale of a one-week schedule show that the proposed algorithm has great performance in solving the concerned problem and outperforms its *** high accuracy and efficiency imply its great potential to be applied to solve industrial-size group scheduling problems.

关键词： Insertion-based local search iterated greedy algorithm machine learning memetic algorithm nondominated sorting genetic algorithm II(NSGA-II) production scheduling

来源：评论

学校读者我要写书评

暂无评论

Fast heuristics for minimizing the makespan in non-permutation flow shops

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 100卷 230-243页

作者： Benavides, Alexander J. Ritt, Marcus Univ Nacl San Agustin Arequipa Escuela Profes Ciencia Comp Ave Venezuela S-N Area Ingn Arequipa Peru Univ Fed Rio Grande do Sul Inst Informat Ave Bento Gonalves 9500 BR-91501970 Porto Alegre RS Brazil

We introduce a new permutation representation for non-permutation schedules, and show how the acceleration technique of Taillard can be extended to it. We propose three new heuristics for the non permutation flow shop scheduling problem with makespan minimization: a constructive heuristic with the same time complexity as the well-known NEH heuristic, a non-permutation insertion local search with a time complexity O(n(2)m) for evaluating a neighbourhood on n jobs and m machines, the same as for the permutation insertion local search, and a reduced-neighbourhood best-improvement non permutation local search with a time complexity of O(nm) per neighbourhood. These heuristics are combined into iterated greedy algorithms for the permutation and non-permutation flow shop scheduling problem. In extensive computational experiments we find that our iterated greedy algorithms produce better non-permutation schedules than other methods for the permutation and non-permutation flow shop scheduling problem, in the same computational time. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Scheduling Metaheuristics Flow shop Non-permutation schedules Makespan iterated greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

A hybrid genetic algorithm for distributed hybrid blocking flowshop scheduling problem

引用

JOURNAL OF MANUFACTURING SYSTEMS 2023年 71卷 390-405页

作者： Sun, Xueyan Shen, Weiming Vogel-Heuser, Birgit Huazhong Univ Sci & Technol Wuhan Peoples R China Tech Univ Munich Garching Germany

This paper addresses a distributed hybrid blocking flowshop scheduling problem (DHBFSP) with makespan criterion. Based on the distributed hybrid flowshop scheduling problem (DHFSP) and blocking constraints, a mathematical model of mixed integer linear programming for the DHBFSP is proposed, and a hybrid genetic algorithm is developed. Eight new heuristics are defined in the process of population initialization according to the blocking characteristics of the problem, and five heuristic rules are chosen through experiments for population initialization and the rest of the individuals are generated randomly. Offspring individuals are obtained through crossover and mutation operations, while an offspring selection strategy is proposed to make decisions in the population offspring selection. The destruction and reconstruction (DR) operation is performed for the optimal individuals of the offspring population to optimize their individual structures, and a local search method is adopted for the deep search of individuals. Compared with other existing meta-heuristics, the proposed hybrid genetic algorithm performs better on benchmarks and the local search method VND_LS3 has a comprehensively strong search capability.

关键词： Distributed hybrid blocking flowshop scheduling Genetic algorithm iterated greedy algorithm Heuristics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：