Filtering Rules for Flow Time Minimization in a Parallel Machine Scheduling Problem

• URL: http://arxiv.org/abs/2011.10307v1
• Date: Fri, 20 Nov 2020 10:00:14 GMT
• Title: Filtering Rules for Flow Time Minimization in a Parallel Machine Scheduling Problem
• Authors: Margaux Nattaf (G-SCOP), Arnaud Malapert
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the scheduling of jobs of different families on parallel machines with qualification constraints. Originating from semiconductor manufacturing, this constraint imposes a time threshold between the execution of two jobs of the same family. Otherwise, the machine becomes disqualified for this family. The goal is to minimize both the flow time and the number of disqualifications. Recently, an efficient constraint programming model has been proposed. However, when priority is given to the flow time objective, the efficiency of the model can be improved. This paper uses a polynomial-time algorithm which minimize the flow time for a single machine relaxation where disqualifications are not considered. Using this algorithm one can derived filtering rules on different variables of the model. Experimental results are presented showing the effectiveness of these rules. They improve the competitiveness with the mixed integer linear program of the literature.

Related papers

• Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
  This paper presents a novel multi-unmanned aerial vehicle (UAV) assisted collaborative mobile edge computing (MEC) framework.<n>It aims to minimize the system cost, and thus realize an improved trade-off between task consumption and energy consumption.<n>We show that the proposed scheme can significantly reduce the system cost, and thus realize an improved trade-off between task consumption and energy consumption.
  arXiv  Detail & Related papers  (2025-10-23T02:55:40Z)
• 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)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive. LCD can distort the global distribution over strings, sampling tokens based only on local information. We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• A mathematical model for simultaneous personnel shift planning and unrelated parallel machine scheduling [3.0477617036157136]
  This paper addresses a production scheduling problem derived from an industrial use case. It focuses on unrelated parallel machine scheduling with the personnel availability constraint. It assumes shared personnel among machines, with one personnel required per machine for setup and supervision during job processing.
  arXiv  Detail & Related papers  (2024-02-24T01:04:04Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem [12.791789710379057]
  We propose a chance-constrained version of the Makespan Scheduling problem. We investigate the theoretical performance of the classical Randomized Local Search and (1+1) EA for it. More specifically, we first study two variants of the Chance-constrained Makespan Scheduling problem and their computational complexities.
  arXiv  Detail & Related papers  (2022-12-22T04:31:23Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• 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)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• Efficient Temporal Piecewise-Linear Numeric Planning with Lazy Consistency Checking [4.834203844100679]
  We propose a set of techniques that allow the planner to compute LP consistency checks lazily where possible. We also propose an algorithm to perform duration-dependent goal checking more selectively. The resultant planner is not only more efficient, but outperforms most state-of-the-art temporal-numeric and hybrid planners.
  arXiv  Detail & Related papers  (2021-05-21T07:36:54Z)
• Self Normalizing Flows [65.73510214694987]
  We propose a flexible framework for training normalizing flows by replacing expensive terms in the gradient by learned approximate inverses at each layer. This reduces the computational complexity of each layer's exact update from $mathcalO(D3)$ to $mathcalO(D2)$. We show experimentally that such models are remarkably stable and optimize to similar data likelihood values as their exact gradient counterparts.
  arXiv  Detail & Related papers  (2020-11-14T09:51:51Z)
• Accelerating combinatorial filter reduction through constraints [37.032079828955425]
  This paper proposes a new formalization needing only a number of constraints, and characterizes these constraints in three different forms. We show that constraints in conjunctive normal form capture the problem most effectively, leading to a method that outperforms others. To leverage the observation, we introduce just-in-time generation of such constraints, which yields improvements in efficiency and has the potential to minimize large filters.
  arXiv  Detail & Related papers  (2020-11-06T16:52:06Z)
• 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)
• Time-varying Gaussian Process Bandit Optimization with Non-constant Evaluation Time [93.6788993843846]
  We propose a novel time-varying Bayesian optimization algorithm that can effectively handle the non-constant evaluation time. Our bound elucidates that a pattern of the evaluation time sequence can hugely affect the difficulty of the problem.
  arXiv  Detail & Related papers  (2020-03-10T13:28:33Z)

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.