Theoretical Lower Bounds for the Oven Scheduling Problem

• URL: http://arxiv.org/abs/2410.01368v1
• Date: Wed, 2 Oct 2024 09:30:01 GMT
• Title: Theoretical Lower Bounds for the Oven Scheduling Problem
• Authors: Francesca Da Ros, Marie-Louise Lackner, Nysret Musliu,
• Abstract summary: The objective of the problem is to schedule a set of jobs on ovens while minimizing several factors. The key to obtaining efficient schedules is to process compatible jobs simultaneously in batches. We develop theoretical, problem-specific lower bounds for the OSP that can be computed very quickly.
• Score: 6.144680854063938
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Oven Scheduling Problem (OSP) is an NP-hard real-world parallel batch scheduling problem arising in the semiconductor industry. The objective of the problem is to schedule a set of jobs on ovens while minimizing several factors, namely total oven runtime, job tardiness, and setup costs. At the same time, it must adhere to various constraints such as oven eligibility and availability, job release dates, setup times between batches, and oven capacity limitations. The key to obtaining efficient schedules is to process compatible jobs simultaneously in batches. In this paper, we develop theoretical, problem-specific lower bounds for the OSP that can be computed very quickly. We thoroughly examine these lower bounds, evaluating their quality and exploring their integration into existing solution methods. Specifically, we investigate their contribution to exact methods and a metaheuristic local search approach using simulated annealing. Moreover, these problem-specific lower bounds enable us to assess the solution quality for large instances for which exact methods often fail to provide tight lower bounds.

Related papers

• Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach [0.0]
  Resource-Constrained Project Scheduling Problem (RCPSP) with time-of-use energy tariffs (TOU) and machine states.<n>We propose two novel approaches to solve it: a monolithic Constraint Programming (CP) approach and a Logic-Based Benders Decomposition (LBBD) approach.
  arXiv  Detail & Related papers  (2026-01-10T11:47:56Z)
• Constraint programming model and biased random-key genetic algorithm for the single-machine coupled task scheduling problem with exact delays to minimize the makespan [0.0]
  We consider the strongly NP-hard single-machine coupled task scheduling problem with exact delays to minimize the makespan.<n>We model the problem using constraint programming (CP) and propose a biased random-key genetic algorithm (BRKGA)<n>Our BRKGA combines some successful components in the literature: an initial solution generator, periodical restarts and shakes, and a local search algorithm.
  arXiv  Detail & Related papers  (2025-12-29T02:27:45Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex. Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs. We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Parallel splitting method for large-scale quadratic programs [2.520799507359113]
  SPLIT is a framework for decomposing large-scale quadratic programs into smaller subproblems, which are then solved in parallel. We show that SPLIT is capable of providing drastic reductions in computational time, while delivering high-quality solutions.
  arXiv  Detail & Related papers  (2025-03-21T09:45:47Z)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  We present Recipe2Plan, a novel benchmark framework based on real-world cooking scenarios. Unlike conventional benchmarks, Recipe2Plan challenges agents to optimize cooking time through parallel task execution.
  arXiv  Detail & Related papers  (2025-03-04T03:27:02Z)
• Evaluation of Quantum Annealing-based algorithms for flexible job shop scheduling [9.674641730446748]
  A flexible job shop scheduling problem (FJSSP) poses a complex optimization task. approximation methods are employed to ensure solutions are within acceptable timeframes. Quantum Annealing, a metaheuristic leveraging quantum mechanical effects, demonstrates superior solution quality in a shorter time.
  arXiv  Detail & Related papers  (2024-08-28T09:52:14Z)
• Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport [35.440243358517066]
  We introduce novel families of upper and lower bounds for the Optimal Transport problem constructed by aggregating solutions of mini-batch OT problems. The upper bound family contains traditional mini-batch averaging at one extreme and a tight bound found by optimal coupling of mini-batches at the other. Through various experiments, we explore the trade-off between computational budget and bound tightness and show the usefulness of these bounds in computer vision applications.
  arXiv  Detail & Related papers  (2022-10-24T22:12:17Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  Low-rank optimal transport (LOT) approach advocated in citescetbon 2021lowrank LOT is seen as a legitimate contender to entropic regularization when compared on properties of interest. We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
  arXiv  Detail & Related papers  (2022-05-24T20:51:37Z)
• Exact methods and lower bounds for the Oven Scheduling Problem [5.7485371212305685]
  The Oven Scheduling Problem (OSP) is a new parallel batch scheduling problem that arises in the area of electronic component manufacturing. Running the ovens is highly energy-intensive and thus the main objective, besides finishing jobs on time, is to minimize the cumulative batch processing time across all ovens. We propose to solve this NP-hard scheduling problem via constraint programming (CP) and integer linear programming (ILP) and present corresponding models.
  arXiv  Detail & Related papers  (2022-03-23T16:28:05Z)
• Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems [30.759279275710078]
  We propose a new and scalable approach to computing index-based solutions. We provide algorithms designed to capture index decay without having to solve the costly finite horizon problem. Our algorithms achieve an over 150x speed-up over existing methods in these tasks without loss in performance.
  arXiv  Detail & Related papers  (2021-03-08T13:10:31Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  We introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. We compare FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis.
  arXiv  Detail & Related papers  (2021-02-17T19:55:42Z)
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
  We propose to use backward mode linear relaxation based analysis (LiRPA) to replace Linear Programming (LP) during the BaB process. Unlike LP, LiRPA when applied naively can produce much weaker bounds and even cannot check certain conflicts of sub-domains during splitting. We demonstrate an order of magnitude speedup compared to existing LP-based approaches.
  arXiv  Detail & Related papers  (2020-11-27T16:42:12Z)
• Filtering Rules for Flow Time Minimization in a Parallel Machine Scheduling Problem [0.0]
  This paper studies the scheduling of jobs of different families on parallel machines with qualification constraints. The goal is to minimize both the flow time and the number of disqualifications. This paper uses a-time algorithm which minimize the flow time for a single machine relaxation where disqualifications are not considered.
  arXiv  Detail & Related papers  (2020-11-20T10:00:14Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining [69.00394670035747]
  Hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques.
  arXiv  Detail & Related papers  (2019-08-28T13:12:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.