Article
Computer Science, Interdisciplinary Applications
Moritz Buchem, Tjark Vredeveld
Summary: The study investigates the application of fixed assignment policies in stochastic online scheduling problems to minimize total weighted expected completion time on uniform parallel machines. By introducing specific lower bounds for the uniform machine environment, performance guarantees are improved. In the Online-List model, it is shown that a greedy assignment policy is asymptotically optimal. Finally, a computational study is conducted to evaluate the performance of these policies in practice.
COMPUTERS & OPERATIONS RESEARCH
(2021)
Article
Computer Science, Artificial Intelligence
Raka Jovanovic, Stefan Voss
Summary: This paper discusses the problem of minimizing makespan on unrelated parallel machines with sequence-dependent setup times and introduces a novel population-based metaheuristic method called FSS. Experimental results show that FSS outperforms GRASP, ACO and WO significantly on standard benchmark instances.
APPLIED SOFT COMPUTING
(2021)
Article
Computer Science, Software Engineering
Jesper Nederlof, Celine M. F. Swennenhuis
Summary: This paper focuses on the study of partial scheduling problems, aiming to determine the complexity and find algorithms with minimal runtime for different variants. The research presents optimal runtimes for many interesting cases and provides a time algorithm to solve partial scheduling problems.
Article
Computer Science, Interdisciplinary Applications
Istvan Modos, Premysl Sucha, Zdenek Hanzalek
Summary: This study focuses on discrete manufacturing scheduling problem with energy consumption limits, analyzing the computational complexity and proposing an adaptive local search heuristic algorithm that outperforms existing models in experiments.
COMPUTERS & INDUSTRIAL ENGINEERING
(2021)
Article
Engineering, Industrial
Dehua Xu, Limin Xu, Zhijun Xu, Xianyu Yu
Summary: The authors demonstrate by counterexample that the binary integer quadratic programming model proposed by Kaabi and Harrath is incorrect, and they provide two linear models as the correct alternatives.
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
(2021)
Article
Management
Antonin Novak, Premysl Sucha, Matej Novotny, Richard Stec, Zdenek Hanzalek
Summary: We studied a stochastic parallel machine scheduling problem and developed novel lower and upper bounds to solve the difficult task. With a scalable method and efficient branch-and-price algorithm, we achieved optimal solutions for instances with 500 jobs within seconds.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Computer Science, Interdisciplinary Applications
Miguel Cezar Santoro, Leonardo Junqueira
Summary: In this paper, we propose novel mixed integer linear programming models for the unrelated parallel machine scheduling problem with calendar. The models aim to minimize the makespan and consider various constraints and possibilities. The models are evaluated using a state-of-the-art solver and show promising results in handling instances in realistic situations.
COMPUTERS & INDUSTRIAL ENGINEERING
(2023)
Article
Operations Research & Management Science
Alan J. Soper, Vitaly A. Strusevich
Summary: This study provides a parametric analysis of scheduling on three uniform parallel machines to minimize the makespan with at most one preemption compared to the global optimal schedule with any number of preemptions. A tight bound is derived based on the relative speeds of the machines when two of them have the same speed.
ANNALS OF OPERATIONS RESEARCH
(2021)
Article
Management
Ran Lin, Jun-Qiang Wang, Ammar Oulamara
Summary: This article addresses an online scheduling problem for identical parallel-batch machines with periodic availability constraints and job delivery. The machines can process multiple jobs simultaneously in a batch without preemption and have alternating available and unavailable time intervals. Jobs are released over time, and after completion, they are delivered to customers. Three objective functions are considered, and this article provides lower bounds on competitive ratios, online algorithms, and analyzes their competitive ratios.
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE
(2023)
Article
Computer Science, Artificial Intelligence
J. Adan
Summary: This paper proposes a new hybrid genetic algorithm for the unrelated parallel machine scheduling problem and demonstrates its superiority through a comparative study on large instances. It also highlights the importance of calibration.
JOURNAL OF INTELLIGENT MANUFACTURING
(2022)
Article
Computer Science, Information Systems
Zhen Zhang, Jinchuan Zhang, Lingzhi Zhu
Summary: The study proposes an FPT(k)-time approximation algorithm for chromatic k-median problem, achieving a (3+epsilon)-approximation. The key step in obtaining parameterized approximation is using a different random sampling algorithm for opening facilities.
Article
Automation & Control Systems
Zixiao Pan, Deming Lei, Ling Wang
Summary: This article proposes a knowledge-based two-population optimization (KTPO) algorithm to solve the distributed energy-efficient parallel machines scheduling problem (DEPMSP). It derives five properties by analyzing the characteristics of DEPMSP, initializes the population using problem-specific knowledge-based heuristics and a random heuristic, and proposes two knowledge-based local search operators to enhance the exploitation.
IEEE TRANSACTIONS ON CYBERNETICS
(2022)
Article
Computer Science, Artificial Intelligence
Kai Li, Han Zhang, Chengbin Chu, Zhao-hong Jia, Jianfu Chen
Summary: This paper addresses the problem of scheduling a group of jobs on uniform parallel batch processing machines with non-identical machine capacities and different unit pollution emission costs, aiming to minimize the maximum lateness and the total pollution emission costs. A discrete bi-objective evolutionary algorithm C-NSGA-A is developed to solve this problem, with a constructive individual generation method and an angle-based environmental selection strategy to improve algorithm performance.
EXPERT SYSTEMS WITH APPLICATIONS
(2022)
Article
Operations Research & Management Science
Ilan Reuven Cohen, Izack Cohen, Iyar Zaks
Summary: This research proposes a polynomial-time algorithm with a constant approximation ratio for minimizing the weighted sum of job completion times for capacitated parallel machines. The algorithm prioritizes jobs based on the smallest volume-by-weight ratio and offers provable approximation guarantees.
ANNALS OF OPERATIONS RESEARCH
(2023)
Article
Operations Research & Management Science
Mostafa Khatami, Daniel Oron, Amir Salehipour
Summary: This paper introduces the problem of scheduling a set of coupled-task jobs on parallel identical machines with the objective of minimizing makespan in the context of patient appointment scheduling. The majority of these problems are proven to be (strongly) NP-hard, but optimal scheduling policies are provided for two settings consisting of identical jobs. An important result is that the existence of a (2-ε)-approximation algorithm for the problem implies P=NP, improving a recently proposed bound for the open-shop counterpart.
OPTIMIZATION LETTERS
(2023)
Article
Operations Research & Management Science
Tomas Gavenciak, Martin Koutecky, Dusan Knop
Summary: Powerful results from the theory of integer programming have led to substantial advances in parameterized complexity. However, there is still limited understanding in the parameterized complexity community of the strengths and limitations of the available tools. This study aims to address this issue by providing a quick reference guide of integer programming algorithms and demonstrating their applications in three case studies.
DISCRETE OPTIMIZATION
(2022)
Article
Operations Research & Management Science
Martin Koutecky, Asaf Levin, Syed M. Meesum, Shmuel Onn
Summary: This article studies the problem of separable multichoice optimization and provides approximate solutions on monotone systems. The results show that these problems can be solved with close-to-optimal solutions in polynomial time.
DISCRETE OPTIMIZATION
(2022)
Article
Computer Science, Theory & Methods
Robert Bredereck, Klaus Heeger, Dusan Knop, Rolf Niedermeier
Summary: In this paper, we investigate the parameterized complexity analysis of the NP-hard STABLE ROOMMATES WITH TIES AND INCOMPLETE LISTS problem and present several important results. We show that computing a maximum-cardinality stable matching is hard for acceptability graphs with bounded treedepth, bounded tree-cut width, and bounded disjoint paths modulator number. Furthermore, we demonstrate that asking for perfect stable matchings or the mere existence of a stable matching is fixed-parameter tractable with respect to tree-cut width but not with respect to treedepth. Additionally, we provide fixed-parameter tractability results for the parameter feedback edge set number.
INFORMATION AND COMPUTATION
(2022)
Article
Computer Science, Software Engineering
Dusan Knop, Martin Koutecky, Asaf Levin, Matthias Mnich, Shmuel Onn
Summary: This paper studies high-multiplicity N-fold integer programs and presents a corresponding algorithm. The algorithm is capable of solving this type of problem in polynomial time based on the size of the succinct encoding, which can be significantly smaller than the size of the explicit instance. Furthermore, the paper introduces a novel proximity theorem and generalizes a fundamental notion.
MATHEMATICAL PROGRAMMING
(2023)
Article
Operations Research & Management Science
Vaclav Blazej, Pratibha Choudhary, Dusan Knop, Jan Matyas Kristian, Ondrej Suchy, Tomas Valla
Summary: This work focuses on solving the tracking paths problem in vertex-weighted graphs. A 6-approximation algorithm is derived for weighted graphs, and a 4-approximation algorithm is obtained for unweighted graphs. It is the first constant factor approximation for this problem.
DISCRETE OPTIMIZATION
(2023)
Article
Computer Science, Information Systems
Vaclav Blazej, Pratibha Choudhary, Dusan Knop, Jan Matyas Kristan, Ondrej Suchy, Tomas Valla
Summary: This paper presents a polynomial size kernel and a kernel in planar graphs for the TRACKING SHORTEST PATHS problem, along with a single exponential algorithm for solving the problem in planar graphs.
INFORMATION PROCESSING LETTERS
(2023)
Correction
Computer Science, Theory & Methods
Piotr Faliszewski, Rica Gonen, Martin Koutecky, Nimrod Talmon
JOURNAL OF LOGIC AND COMPUTATION
(2023)
Article
Automation & Control Systems
Niclas Boehmer, Robert Bredereck, Dusan Knop, Junjie Luo
Summary: Given a set of agents with qualifications, this study aims to identify a socially qualified subgroup based on specific aggregation rules. The article provides a comprehensive understanding of the computational complexity landscape and explores various aspects of bribery, including cost, price, and goals.
AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS
(2023)
Proceedings Paper
Computer Science, Software Engineering
Rica Gonen, Martin Koutecky, Roei Menashof, Nimrod Talmon
Summary: This research focuses on a more complex model of opinion diffusion, considering approval-based or ordinal-based preferences and diffusion processes influenced by local voting rules. The proposed greedy and local search heuristics perform well on real world and synthetic instances, with different parameters affecting the runtime and quality of solutions.
SOFSEM 2023: THEORY AND PRACTICE OF COMPUTER SCIENCE
(2023)
Article
Computer Science, Artificial Intelligence
Robert Ganian, Thekla Hamm, Dusan Knop, Simon Schierreich, Ondrej Suchy
Summary: This article introduces a variant of hedonic games called hedonic diversity games, which aims to better model diversity and fairness. New algorithms are designed and parameterized complexity analysis is provided for computing the outcomes of these games.
ARTIFICIAL INTELLIGENCE
(2023)
Proceedings Paper
Computer Science, Artificial Intelligence
Dusan Knop, Simon Schierreich, Ondrej Suchy
Summary: The study proposes a new discrete model and presents a problem based on social networks. The goal of the study is to add as few agents as possible to initially given seed-sets so that each agent either has both opinions or none. The computational complexity of the problem is explored, and it is found to be a challenging problem. Further investigation is conducted from a parametrized perspective.
THIRTY-SIXTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FOURTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE / TWELVETH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE
(2022)
Proceedings Paper
Computer Science, Artificial Intelligence
Vaclav Blazej, Dusan Knop, Simon Schierreich
Summary: Information diffusion in social networks is a well-studied concept. This study proposes the study of the diffusion of two secrets in a heterogeneous environment and explores parameterized approaches.
THIRTY-SIXTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FOURTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE / TWELVETH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE
(2022)
Proceedings Paper
Computer Science, Artificial Intelligence
Robert Ganian, Thekla Hamm, Dusan Knop, Simon Schierreich, Ondrej Suchy
Summary: This paper investigates a variant of Hedonic games called Hedonic diversity games, aiming to better explore diversity and fairness. By designing new algorithms and providing lower bounds, a complete parameterized-complexity picture is presented for computing Nash and individually stable outcomes. The study reveals that, apart from two trivial cases, a necessary condition for tractability in Hedonic diversity games is that the number of colors is bounded by the parameter.
THIRTY-SIXTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FOURTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE / THE TWELVETH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE
(2022)
