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

Multi-Period Service Scheduling Problems: A New Model and Heuristic Approaches of Relax-and-fix and fix-and-optimize

引用

IEEE LATIN AMERICA TRANSACTIONS 2021年第9期19卷 1528-1536页

作者： Oliveira, J. Scarpin, C. Univ Estadual Ctr Oeste UNICENTRO Irati Parana Brazil Res Grp Technol Appl Optimizat GTAO Irati Parana Brazil Univ Fed Parana UFPR Dept Adm Geral & Aplicada DAGA Curitiba Parana Brazil Grp Pesquisa Tecnol Aplicada Otimizacao GTAO Curitiba Parana Brazil

Multi-Period Service Scheduling Problem MSSP is descibed as a category of problems that arise in the context of scheduling services. In these problems, customers have a periodic service to be attended, a finite number of times, within the time horizon. The Multi-Period Multi-Service Scheduling Problem MMSSP is presented as an alternative formulation for MSSP, in which the resolution of an MMSSP is equivalent to the resolution of multiple MSSP, demonstrating the complexity of solving this pattern. The presented formulation can lead several applications in different areas. To solve this new pattern, the Relax-and-fix and fix-and-optimize strategies are used. In these heuristics, part of the entire variables are fixed and/or relaxed interactively. To assess the efficiency of the strategies, a set of 150 small, medium and large instances are generated and resolved. The results of extensive experiments demonstrate that heuristics produce quality solutions, highlighting a good balance between optimization and computational time.

关键词： Computational modeling Processor scheduling Surges Optimization IEEE transactions Scheduling Routing Heuristic Multi-period service scheduling Relax-and-fix fix-and-optimize Scheduling

来源：评论

学校读者我要写书评

暂无评论

A fix-and-optimize heuristic for the high school timetabling problem

引用

COMPUTERS & OPERATIONS RESEARCH 2014年第PartA期52卷 29-38页

作者： Dorneles, Arton P. de Araujo, Olinto C. B. Buriol, Luciana S. Univ Fed Rio Grande do Sul Inst Informat BR-91501970 Porto Alegre RS Brazil Univ Fed Santa Maria Colegio Tecn Ind Santa Maria BR-97105900 Santa Maria RS Brazil

The high school timetabling is a classical combinatorial optimization problem that takes a large number of variables and constraints into account Due to its combinatorial nature, solving medium and large instances to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Among the different requirements that are considered in Brazilian schools, two compactness requirements must be met on a teacher's schedule: the minimization of working days and the avoidance of idle timeslots. In this paper, we present a mixed integer linear programming model and a fix-and-optimize heuristic combined with a variable neighborhood descent method. Our method uses three different types of decompositions - class, teacher and day - in order to solve the high school timetabling problem. The method is able to find new best known solutions for seven instances, including three optimal ones. A comparison with results reported in the literature shows that the proposed fix-and-optimize heuristic outperforms state-of-the-art techniques for the resolution of the problem at hand. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： High school timetabling Mixed integer linear programming fix-and-optimize Variable neighborhood descent Matheuristics ITC-2011

来源：评论

学校读者我要写书评

暂无评论

A fix-and-optimize matheuristic for the k-labelled spanning forest problem

A fix-and-optimize matheuristic for the k-labelled spanning ...

引用

IEEE Congress on Evolutionary Computation (CEC)

作者： Pinheiro, Tiago F. D. Ravelo, Santiago, V Buriol, Luciana S. Univ Fed Rio Grande do Sul Inst Informat Porto Alegre RS Brazil Amazon Com Seattle WA USA

ISBN: (数字)9781665467087

ISBN: (纸本)9781665467087

In this paper, we study the k-labeled spanning forest problem (KLSF). The input for this problem is an undirected graph with labeled edges and a positive integer k. The goal is to find a spanning forest of the graph with at most k different labels associated with the edges, minimizing the number of components. KLSF finds practical applications in different scenarios related to networks design and telecommunications. Solving it may help to reduce the negative impact of electromagnetic fields exposure on the population health or to increase profits of internet management companies, among others. The interest in KLSF is not only practical but also theoretical since the problem generalizes the best-known NP-hard minimum labeling spanning tree problem (MLST). To approach KLSF, we propose a fix-and-optimize matheuristic that was tested over several instances, achieving high-quality solutions in reasonable computational time. When compared to the best-known algorithms in the literature, our matheuristic outperformed the other proposals in most cases, finding better solutions in less computational time for the most challenging instances.

关键词： fix-and-optimize Matheuristic Integer Linear Program k-Labeled Spanning Forest

来源：评论

学校读者我要写书评

暂无评论

Robust optimization of risk-aware, resilient and sustainable closed-loop supply chain network design with Lagrange relaxation and fix-and-optimize

引用

INTERNATIONAL JOURNAL OF LOGISTICS-RESEARCH AND APPLICATIONS 2024年第5期27卷 705-745页

作者： Lotfi, Reza Sheikhi, Zohre Amra, Mohsen AliBakhshi, Mehdi Weber, Gerhard-Wilhelm Yazd Univ Dept Ind Engn Yazd Iran Behineh Gostar Sanaye Arman Tehran Iran Sharif Univ Technol Dept Ind Engn Tehran Iran Islamic Azad Univ South Tehran Branch Dept Ind Engn Tehran Iran Tarbiat Modares Univ Dept Ind Engn Tehran Iran Poznan Univ Tech Fac Engn Management Poznan Poland METU IAM Ankara Turkiye

This study explores a Robust, Risk-aware, Resilient, and Sustainable Closed-Loop Supply Chain Network Design (3RSCLSCND) to tackle demand fluctuation like COVID-19 pandemic. A two-stage robust stochastic multiobjective programming model serves to express the proposed problems in formulae. The objective functions include minimising costs, CO2 emissions, energy consumption, and maximising employment by applying Conditional Value at Risk (CVaR) to achieve reliability through risk reduction. The Entropic Value at Risk (EVaR) and Minimax method are used to compare with the proposed model. We utilise the Lp-Metric method to solve the multiobjective problem. Since this model is complex, the Lagrange relaxation and fix-and-Optimise algorithm are applied to find lower and upper bounds in large-scale, respectively. The results confirm the superior power of the model offered in estimating costs, energy consumption, environmental pollution, and employment level. This model and algorithms are applicable for other CLSC problems.

关键词： Closed-loop supply chain sustainability resiliency risk Lagrangian relaxation fix-and-optimize

来源：评论

学校读者我要写书评

暂无评论

A fix-and-optimize heuristic for the Unrelated Parallel Machine Scheduling Problem

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 163卷

作者： Fonseca, George H. G. Figueiroa, Guilherme B. Toffolo, Tulio A. M. Univ Fed Ouro Preto Dept Comp & Syst Ouro Preto Brazil Univ Fed Ouro Preto Dept Comp Ouro Preto Brazil

This paper proposes and evaluates a matheuristic approach for the Unrelated Parallel Machine Scheduling Problem (UPMSP). The UPMSP consists of assigning jobs to unrelated parallel machines considering different processing times for the same job in different machines. Additionally, a setup time is considered between the execution of jobs in the same machine. The problem is addressed by a fix-and-optimize matheuristic that iteratively selects a subset of variables to be fixed to their current values so that the remaining variables will compose a subproblem to be optimized by a mathematical programming solver. In the proposed approach, each subproblem consists of a subset of jobs that are assigned to a subset of machines in the incumbent solution. The subproblems are solved by the state -of -the -art exact algorithm for the UPMSP. In the experiments conducted on benchmark instances, the proposed fix-and-optimize algorithm achieved remarkable results. It outperformed the standalone exact algorithm by a large margin and resulted in competitive solutions when compared to the literature's best-performing heuristic method for the problem. The proposed algorithm obtained the best solution for 669 out of the 1000 instances addressed in this work. Among them, 338 are new best-known solutions. In general, the proposed approach excels at solving instances with a high number of jobs per machine - it resulted in the best solution for 89% of the instances with a ratio of 10 or more jobs per machine in total.

关键词： UPMSP fix-and-optimize Machine scheduling problem

来源：评论

学校读者我要写书评

暂无评论

Multi-Period Profit-Oriented Location Routing Problem in Multi-User Warehouses with Backordering and Order Acceptance: A Relax-fix-optimize Heuristic

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2024年第0期

作者： Ech-Charrat, Mohammed Rida Zhani, Najlae Chargui, Kaoutar Zouadi, Tarik Univ Abdelmalek Essaadi ENSATE Tetouan Morocco Int Univ Rabat Rabat Business Sch BEAR Lab Sala Al Jadida 11100 Morocco

This paper addresses profit maximization in location routing problem (LRP) where backordering is allowed and serving all customers is not mandatory. The problem is motivated by the practical case of distribution companies using temporary multi-user warehouses to serve their customers. We propose a multi-period novel mixed integer linear programming (MILP) model for the problem where demand is price sensitive. The model seeks to find optimal locations of warehouses over the planning horizon, set of orders to serve, to backorder or to reject, and routing decisions giving optimal profit. The commercial solver (CPLEX) is used to solve the model on small instances. For medium and large instances, we propose a solution approach that incorporates the Relax and fix (R&F), fix and optimize (F&O) procedures combined with local search heuristics. Computational experiments and economic analysis show the relevance of the proposed approach and the impact of parameters on generated profit.

关键词： Location routing problem backordering profit maximization price-sensitive demand mixed linear integer programming relax and fix fix-and-optimize local search

来源：评论

学校读者我要写书评

暂无评论

Relax-fix-optimize heuristics for time-relaxed sports timetabling

引用

INFOR 2021年第4期59卷 623-638页

作者： Van Bulck, David Goossens, Dries Univ Ghent Fac Econ & Business Adm B-9000 Ghent Belgium

Time-relaxed sports timetables utilize (many) more time slots than there are games per team, and therefore offer the flexibility to take into account player and venue availability. However, time-relaxed tournaments also have the drawback that the difference in games played per team and the rest period between teams' consecutive games can vary considerably. In addition, organisers may want to avoid consecutive home and away games (i.e. breaks). To construct fair timetables, we propose relax-and-fix (R&F) and fix-and-optimize (F&O) heuristics that make use of team- and time-based variable partitioning schemes. While the team-based R&F constructs a timetable by gradually taking into account the integrality constraints related to all home games of a subset of teams, the time-based R&F maintains a rolling horizon of time intervals in which the integrality constraints of all games scheduled within the time interval are activated. The F&O heuristics use the same variable partitioning schemes, but they never relax the integrality constraints and allow to recover from mistakes by making a small number of changes with respect to the variables optimized in previous iterations. For numerous real-life instances, our heuristics generate high-quality timetables using only a fraction of the computational resources used by monolithic integer programming solvers.

关键词： Time-relaxed sports scheduling relax-and-fix fix-and-optimize round-robin tournaments availability constraints

来源：评论

学校读者我要写书评

暂无评论

A metaheuristic algorithm for efficient aircraft sequencing and scheduling in terminal maneuvering areas

引用

OPTIMIZATION LETTERS 2025年第3期19卷 579-604页

作者： Gui, Dongdong Le, Meilong Luo, Xiaodong Huang, Zhouchun Nanjing Univ Aeronaut & Astronaut Coll Civil Aviat Nanjing Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Econ & Management Nanjing Peoples R China Shenzhen Res Inst Big Data Shenzhen Peoples R China

Air traffic controllers face a daily challenge ensuring the safe and orderly flow of aircraft in terminal maneuvering areas, known academically as the Aircraft Sequencing and Scheduling Problem (ASSP). Typically formulated as a mixed integer linear programming problem, the strong NP-hard nature of the ASSP necessitates the use of heuristics or metaheuristics for practical, time-efficient solutions. In this paper, we propose a new metaheuristic algorithm to address the computational complexity of the problem. The algorithm employs a single-solution-based search methodology that starts from a well-constructed initial solution and iteratively explores a fix-and-optimize procedure to find an improved solution. Specifically, this procedure solves a variant of the ASSP that contains all the continuous variables and a selected subset of binary variables of the original problem, with the remaining binary variables being temporarily fixed to the values determined based on previous iterations. Additionally, the algorithm incorporates tabu search to increase the possibility of quickly finding optimal solutions. A rolling horizon control approach further accelerates the solution derivation process by decomposing the original problem into smaller subproblems. Our computational experiments using real traffic data from Guangzhou Baiyun International Airport demonstrates the effectiveness of the algorithm in terms of solution quality and computational time.

关键词： Aircraft sequencing and scheduling Metaheuristic algorithm Mixed integer linear programming fix-and-optimize

来源：评论

学校读者我要写书评

暂无评论

An effective population-based approach for the partial set covering problem

引用

JOURNAL OF HEURISTICS 2025年第1期31卷 1-32页

作者： Zhang, Ye He, Jinlong Zhou, Yupeng Hu, Shuli Cai, Dunbo Tian, Naiyu Yin, Minghao Northeast Normal Univ Coll Informat Sci & Technol Changchun 130117 Peoples R China China Mobile Suzhou Software Technol Co Ltd Ctr Technol Res & Innovat Suzhou 215000 Peoples R China Nanjing Res Inst Elect Engn Nanjing 210007 Peoples R China

The partial set covering problem (PSCP) is a significant combinatorial optimization problem that finds applications in numerous real-world scenarios. The objective of PSCP is to encompass a minimum number of subsets while ensuring the coverage of at least n elements. Due to its NP-hard nature, solving large-scale PSCP efficiently remains a critical issue in computational intelligence. To effectively tackle this challenge, we delve into a population-based approach that incorporates a modified tabu search, thereby striking a delicate balance between exploration and exploitation. To further enhance its efficacy, we employ the multiple path-relinking strategy and the fix-and-optimize process. Finally, the dynamic resource allocation scheme is utilized to save computing efforts. Comparative experiments of the proposed algorithm were conducted against three state-of-the-art competitors, across two distinct categories, encompassing 150 instances. The results significantly underscore the profound effectiveness of our proposed algorithm, as evidenced by the updating of 67 best-known solutions. Moreover, we conduct an in-depth analysis of the key components inherent to the algorithm, shedding light on their respective influences on the whole performance.

关键词： Partial set covering Tabu search Multiple path-relinking fix-and-optimize Dynamic resource allocation

来源：评论

学校读者我要写书评

暂无评论

Inbound and outbound flow integration for cross-docking operations

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第3期294卷 1153-1163页

作者： Coindreau, Marc-Antoine Gallay, Olivier Zufferey, Nicolas Laporte, Gilbert Univ Lausanne Dept Operat Fac Business & Econ HEC Lausanne Quartier UNIL Chamberonne CH-1015 Lausanne Switzerland Univ Geneva Geneva Sch Econ & Management Unimail CH-1211 Geneva 4 Switzerland HEC Montreal 3000 Chemin Cote St Catherine Montreal PQ H3C 3J7 Canada Ctr Interuniv Rech Reseaux Entreprise Logist & Tr Montreal PQ Canada Univ Bath Bath BA2 7AY Avon England

Keywords: Logistics Cross-dock scheduling Matheuristic fix-and-optimize

关键词： Logistics Cross-dock scheduling Matheuristic fix-and-optimize

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：