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

New meta-heuristic for dynamic scheduling in permutation flowshop with new order arrival

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2018年第5-8期98卷 1817-1830页

作者： Liu, Weibo Jin, Yan Price, Mark China Univ Petr Acad Chinese Energy Strategy Beijing 102249 Peoples R China Queens Univ Belfast Sch Mech & Aerosp Engn Ashby Bldg Belfast BT9 5AH Antrim North Ireland

Permutation flowshop scheduling problem (PFSP) has attracted lots of attention from both academia and industry as it finds many applications especially for today's mass customization. The PFSP is proved NP-hard, and the dynamic uncertainties such as stochastic new order arrivals significantly increase the problem complexity and difficulty. Many enterprises often struggle to make decisions on accepting new orders and setting due dates for them due to lack of effective scheduling methods. To fill in the knowledge gap, this paper is to propose a new meta-heuristic algorithm which is based on a new enhanced destruction and construction method and a novel repair method while adopting the architecture of the iterated greedy algorithm. Statistical tests were conducted and results show that the new algorithm outperforms existing ones.

关键词： Dynamic scheduling New order Permutation flowshop iterated greedy algorithm Order mixing

来源：评论

学校读者我要写书评

暂无评论

Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2017年 113卷 160-184页

作者： Ye, Song Zhao, Ning Li, Kaidian Lei, Chuanjin Univ Sci & Technol Beijing Sch Mech Engn Xueyuan Rd 30 Beijing 100083 Peoples R China

Flow-shop scheduling problem is an attractive subject in the scheduling field, which has attracted the attention of many researchers in the past five decades. However, few studies focused on non permutation flow-shop problems with time lag consideration. In the present work, the non permutation flow-shop scheduling problem with time lags has been studied to minimize the makespan as a performance measure. First, we obtain a near-optimal permutation solution using the permutation flow-shop problem (PFSP) heuristic. Then, an effective iterated greedy heuristic, which can identify high quality non-permutation solutions, is presented. Using the neighbourhood non-PFSP searching heuristic, we searched for non-PFSP schedules using the proposed heuristic algorithms in the second stage. Finally, the computational results were used to evaluate the performance and effectiveness of the proposed heuristic. The proposed heuristics were able to find near optimal non-PFSP solutions with very short computational time. Thus, the proposed algorithms is efficient and can be used in industrial applications. Moreover, the proposed heuristic algorithms are very simple to implement, which is attractive for industrial applications. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Non-permutation Flow shop Time lags Makespan iterated greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

A new method for a class of parallel batch machine scheduling problem

引用

FLEXIBLE SERVICES AND MANUFACTURING JOURNAL 2022年第2期34卷 518-550页

作者： Jiang, Wei Shen, Yilan Liu, Lingxuan Zhao, Xiancong Shi, Leyuan Peking Univ Dept Ind Engn & Management Beijing 100871 Peoples R China Beijing Res Inst Automat Machinery Ind Co Ltd Beijing 100120 Peoples R China Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA

This paper studies the scheduling problem of jobs with release times, non-identical sizes, and incompatible job families on unrelated parallel batch machines. The capacities of batch machines and the processing times of each job on the batch machines are different. The processing time of one batch is equal to the longest processing time of jobs in this batch. Different types of jobs are not allowed to be assigned into the same batch, which is known as incompatible job families. Mixed integer linear programming and constraint programming (CP) models are proposed. A new batch-based local search method is designed and an iterated greedy (IG) algorithm is developed to avoid unreasonable exchanging of jobs during the local search. Numerical results show that the CP method can obtain high quality solutions in the small-scale instances. For the large-scale instances, the IG algorithm with the new local search method has a competitive performance.

关键词： Batch scheduling Unrelated parallel batch machines Incompatible job families Constraint programming iterated greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

A hybrid algorithmic model for the minimum weight dominating set problem

引用

SIMULATION MODELLING PRACTICE AND THEORY 2016年 64卷 57-68页

作者： Bouamama, Salim Blum, Christian Univ Msila Dept Comp Sci Msila 28000 Algeria Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence San Sebastian Spain Basque Fdn Sci Ikerbasque Bilbao Spain

iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where-given a vertex-weighted graph-the goal is to identify a subset of the graphs' vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches. (C) 2015 Elsevier B.V. All rights reserved.

关键词： iterated greedy algorithm Minimum weight dominating set problem Hybrid model

来源：评论

学校读者我要写书评

暂无评论

Joint Deployment Optimization and Flight Trajectory Planning for UAV Assisted IoT Data Collection: A Bilevel Optimization Approach

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2022年第11期23卷 21492-21504页

作者： Han, Shoufei Zhu, Kun Zhou, MengChu Liu, Xiaojing Nanjing Univ Aeronaut & Astronaut Collaborat Innovat Ctr Novel Software Technol & I Nanjing 210016 Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Peoples R China New Jersey Inst Technol Dept Elect & Comp Engn Newark NJ 07102 USA Macau Univ Sci & Technol Inst Syst Engn Macau Peoples R China Macau Univ Sci & Technol Collaborat Lab Intelligent Sci & Syst Macau Peoples R China

This work investigates an unmanned aerial vehicle (UAV) assisted IoT system, where a UAV flies to each foothold to collect data from IoT devices, and then return to its start point. For such a system, we aim to minimize the energy consumption by jointly optimizing the deployment and flight trajectory of UAV. It is a mixed-integer non-convex and NP-hard problem. In order to address it, a bilevel optimization approach is proposed, where an upper-level method aims to optimize the deployment of UAV and a lower-level one aims to plan UAV flight trajectory. Specifically, the former optimizes the number and locations of footholds of UAV. This work proposes an improved dandelion algorithm with a novel encoding strategy, in which each dandelion represents a foothold of UAV and the entire dandelion population is seen as an entire deployment. Then, two mutation strategies are designed to adjust the number and locations of footholds. Based on the footholds of the UAV provided by the former, the latter transforms flight trajectory planning into a traveling salesman problem (TSP). This work proposes an iterated greedy algorithm to solve it efficiently. The effectiveness of the proposed bilevel optimization approach is verified on ten instances, and the experimental results show that it significantly outperforms other benchmark approaches.

关键词： Internet of Things Energy consumption Data collection Trajectory Optimization Autonomous aerial vehicles Trajectory planning Bilevel optimization deployment optimization dandelion algorithm flight trajectory planning iterated greedy algorithm machine learning UAV

来源：评论

学校读者我要写书评

暂无评论

The distributed no-idle permutation flowshop scheduling problem with due windows

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2024年第4期43卷 1-32页

作者： Mousighichi, Kasra Avci, Mualla Gonca Dokuz Eylul Univ Grad Sch Nat & Appl Sci Izmir Turkiye Dokuz Eylul Univ Dept Ind Engn TR-35397 Izmir Turkiye

The distributed no-idle permutation flowshop scheduling problem has gained significant attention as a prominent area of research in recent years, particularly in industries where setup operations are so expensive that reactivating the machines is not cost-effective. This study addresses an extension of the distributed permutation flowshop scheduling problem with no-idle and due window constraints. The aim is to determine the job assignments to the factories and their sequences in each factory that provide the minimum total weighted earliness and tardiness (TWET) penalties considering due windows. This study is the first to formulate this problem, offering four different mathematical models, and presents a benchmark to examine different problem cases that may arise in practical applications. Furthermore, to effectively solve the diverse problem instances, two hybrid metaheuristic algorithms based on the iterated greedy are proposed. These metaheuristics exhibit promising capabilities, enabling the solution of problem instances involving up to 500 jobs. To assess the effectiveness of the proposed models and algorithms, extensive numerical experiments are conducted, facilitating a thorough evaluation and comparison of their performances.

关键词： The distributed permutation flowshop scheduling No-idle constraints Due windows Total weighted earliness and tardiness iterated greedy algorithm 90-10 90-11

来源：评论

学校读者我要写书评

暂无评论

Memetic algorithm for solving flexible flow-shop scheduling problems with dynamic transport waiting times

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 139卷 105984-000页

作者： Lei, Chuanjin Zhao, Ning Ye, Song Wu, Xiuli Univ Sci & Technol Beijing Sch Mech Engn Xueyuan Rd 30 Beijing 100083 Peoples R China

Flexible flow-shop scheduling with dynamic transport waiting times (FFSPDW) is a typical flow shop scheduling problem in smart manufacturing system. In this problem, jobs need to be transported by transporters like AGV (Automated Guided Vehicle) to next stage after processing. During transportation, waiting time dynamically occurs for both jobs and transporters, and finally contributes to makespan. The waiting times are conditioned by buffer capacity, machine allocations and production sequence. In order to minimize makespan with consideration of dynamic waiting times, we proposed a waiting time calculation approach to evaluate waiting time and makespan. This approach considers two situations: infinite buffer capacity and zero buffer capacity. Further, we developed a memetic algorithm integrated with waiting time calculation approach to solve FFSPDW. Finally, we verified the algorithm parameters via analysis of variance. Computational results show that the proposed memetic algorithm is able to reach high quality solutions with short computation time. Consequently, the proposed approach is suitable for solving industrial FFSPDW problems.

关键词： Flexible flow-shop scheduling Dynamic waiting times Integrated scheduling iterated greedy algorithm Makespan

来源：评论

学校读者我要写书评

暂无评论

A Variable Block Insertion Heuristic for Solving Permutation Flow Shop Scheduling Problem with Makespan Criterion

引用

algorithmS 2019年第5期12卷 100-100页

作者： Kizilay, Damla Tasgetiren, Mehmet Fatih Pan, Quan-Ke Gao, Liang Yasar Univ Dept Ind Engn TR-35100 Izmir Turkey Istinye Univ Dept Ind & Syst Engn TR-34010 Istanbul Turkey Huazhong Univ Sci & Technol Dept Ind & Mfg Syst Engn Wuhan 430074 Hubei Peoples R China Shanghai Univ Sch Mechatron Engn & Automat Shanghai 200444 Peoples R China

In this paper, we propose a variable block insertion heuristic (VBIH) algorithm to solve the permutation flow shop scheduling problem (PFSP). The VBIH algorithm removes a block of jobs from the current solution. It applies an insertion local search to the partial solution. Then, it inserts the block into all possible positions in the partial solution sequentially. It chooses the best one amongst those solutions from block insertion moves. Finally, again an insertion local search is applied to the complete solution. If the new solution obtained is better than the current solution, it replaces the current solution with the new one. As long as it improves, it retains the same block size. Otherwise, the block size is incremented by one and a simulated annealing-based acceptance criterion is employed to accept the new solution in order to escape from local minima. This process is repeated until the block size reaches its maximum size. To verify the computational results, mixed integer programming (MIP) and constraint programming (CP) models are developed and solved using very recent small VRF benchmark suite. Optimal solutions are found for 108 out of 240 instances. Extensive computational results on the VRF large benchmark suite show that the proposed algorithm outperforms two variants of the iterated greedy algorithm. 236 out of 240 instances of large VRF benchmark suite are further improved for the first time in this paper. Ultimately, we run Taillard's benchmark suite and compare the algorithms. In addition to the above, three instances of Taillard's benchmark suite are also further improved for the first time in this paper since 1993.

关键词： heuristic optimization block insertion heuristic flow shop scheduling iterated greedy algorithm constraint programming mixed integer programming

来源：评论

学校读者我要写书评

暂无评论

Scheduling the distributed assembly flowshop problem to minimize the makespan

Scheduling the distributed assembly flowshop problem to mini...

引用

International Conference on ENTERprise Information Systems (CENTERIS) / International Conference on Project MANagement (ProjMAN) / International Conference on Health and Social Care Information Systems and Technologies (HCist)

作者： Ochi, Hanadi Driss, Olfa Belkahla Inst Super Gest Tunis 41 Ave Liberte Tunis Tunisia Univ Manouba Ecole Super Commerce Tunis Tunis Tunisia Univ Manoouba COSMOS Lab ENSI Manouba Tunisia

In this paper, we studied the distributed assembly permutation flowshop scheduling problem (DAPFSP) with the makespan minimization as objective. We proposed iterated greedy-based approach that is labelled the bounded-search iterated greedy algorithm BSIG. In addition, four local search methods are designed to improve solution quality. The computational results show the effectiveness of BSIG in solving the DAPFSP specially with small instances where BSIG outperforms most of the existing algorithms. (C) 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/) Peer-review under responsibility of the scientific committee of the CENTERIS -International Conference on ENTERprise Information Systems / ProjMAN - International Conference on Project MANagement / HCist - International Conference on Health and Social Care Information Systems and Technologies.

关键词： distributed assembly permutation flowshop scheduling problem (DAPFSP) iterated greedy algorithm optimization makespan

来源：评论

学校读者我要写书评

暂无评论

A Lexicographic Bi-objective Scheduling Problem From Steel Production Systems 3rd

A Lexicographic Bi-objective Scheduling Problem From Steel P...

引用

3rd IFAC Workshop pn Cyber-Physical and Human Systems (CPHS)

作者： Zhao, Ziyan Zhou, MengChu Liu, Shixin Guo, Xiwang Liu, Haoyue Northeastern Univ Coll Informat Sci & Engn State Key Lab Synthet Automat Proc Ind Shenyang 110819 Peoples R China New Jersey Inst Technol Dept Elect & Comp Engn Newark NJ 07102 USA Liaoning Shihua Univ Coll Comp & Commun Engn Fushun 113001 Peoples R China

Wire rod and bar rolling is an essential process in a steel production system (SPS). This work considers a lexicographic bi-objective scheduling problem originated from it. As a medium process in SPS, both the impacts of its upstream process, i.e., release time constraints, and the requirements of its downstream process, i.e., due time constraints, on SPS performance, must be considered. The concerned problem aims to minimize the number of tardy tasks as a main objective and total setup time as a secondary one. It is solved via a two-stage method. The first-stage problem is handled with an off-the-shelf optimization software, and the second one with iterated greedy algorithms (IGAs). We compare the performance of IGAs under different strategies and select the best one to solve it. By comparing the experimental results an exact single-objective method's, this paper shows that the proposed method can solve the problem fast with excellent results in terms of the number of tardy tasks and setup time, i.e., the secondary objective, on average. Its usage can result in significant performance improvement in steel production over the existing practice. Copyright (C) 2020 The Authors.

关键词： Batch process batch scheduling iterated greedy algorithm lexicographic bi-objective optimization steel production systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：