Single and Parallel Machine Scheduling with Variable Release Dates
- URL: http://arxiv.org/abs/2103.01785v1
- Date: Tue, 2 Mar 2021 14:52:28 GMT
- Title: Single and Parallel Machine Scheduling with Variable Release Dates
- Authors: Felix Mohr, Gonzalo Mej\'ia, Francisco Yuraszeck
- Abstract summary: We study a simple extension of the total weighted flowtime problem for single and identical parallel machines.
Our main contribution is that we show the NP- completeness of the problem even for the single machine case.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this paper we study a simple extension of the total weighted flowtime
minimization problem for single and identical parallel machines. While the
standard problem simply defines a set of jobs with their processing times and
weights and assumes that all jobs have release date 0 and have no deadline, we
assume that the release date of each job is a decision variable that is only
constrained by a single global latest arrival deadline. To our knowledge, this
simple yet practically highly relevant extension has never been studied. Our
main contribution is that we show the NP- completeness of the problem even for
the single machine case and provide an exhaustive empirical study of different
typical approaches including genetic algorithms, tree search, and constraint
programming.
Related papers
- Zero-Shot Generalization during Instruction Tuning: Insights from Similarity and Granularity [84.12126298229866]
We show that zero-shot generalization during instruction tuning happens very early.
We also show that encountering highly similar and fine-grained training data earlier during instruction tuning, without the constraints of defined "tasks", enables better generalization.
For the first time, we show that zero-shot generalization during instruction tuning is a form of similarity-based generalization between training and test data at the instance level.
arXiv Detail & Related papers (2024-06-17T16:40:21Z) - 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) - Minimalistic Predictions to Schedule Jobs with Online Precedence
Constraints [117.8317521974783]
We consider non-clairvoyant scheduling with online precedence constraints.
An algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed.
arXiv Detail & Related papers (2023-01-30T13:17:15Z) - Answer-Set Programming for Lexicographical Makespan Optimisation in
Parallel Machine Scheduling [18.286430978487388]
We deal with a challenging scheduling problem on parallel machines with sequence-dependent setup times and release dates.
We put the individual machine spans in non-ascending order and lexicographically minimise the resulting robustnesss.
Our experimental results show that ASP is indeed a promising KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers.
arXiv Detail & Related papers (2022-12-18T12:43:24Z) - Structural Analysis of Branch-and-Cut and the Learnability of Gomory
Mixed Integer Cuts [88.94020638263467]
The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers.
We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to the input integer program.
Our main application of this analysis is to derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during branch-and-cut.
arXiv Detail & Related papers (2022-04-15T03:32:40Z) - 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) - Learning to solve the single machine scheduling problem with release
times and sum of completion times [0.76146285961466]
We focus on the solution of a hard single machine scheduling problem by new algorithms embedding techniques from machine learning field and scheduling theory.
Theses transform an instance of the hard problem into an instance of a simpler one solved to optimality.
arXiv Detail & Related papers (2021-01-04T16:40:18Z) - Metaheuristics for the Online Printing Shop Scheduling Problem [0.0]
This real scheduling problem, that emerged in the nowadays printing industry, corresponds to a flexible job shop scheduling problem with sequencing flexibility.
A local search strategy and metaheuristic approaches for the problem are proposed and evaluated.
Numerical experiments with classical instances of the flexible job shop scheduling problem show that the introduced methods are also competitive when applied to this particular case.
arXiv Detail & Related papers (2020-06-22T15:38:00Z) - 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) - Exact and heuristic methods for the discrete parallel machine scheduling
location problem [0.0]
The problem consists in choosing the locations of $p$ machines among a finite set of candidates and scheduling a set of jobs on these machines.
It is proposed a new arc-flow formulation, a column generation and three procedures that are evaluated through extensive computational experiments.
arXiv Detail & Related papers (2020-06-09T00:10:18Z) - The empirical duality gap of constrained statistical learning [115.23598260228587]
We study the study of constrained statistical learning problems, the unconstrained version of which are at the core of virtually all modern information processing.
We propose to tackle the constrained statistical problem overcoming its infinite dimensionality, unknown distributions, and constraints by leveraging finite dimensional parameterizations, sample averages, and duality theory.
We demonstrate the effectiveness and usefulness of this constrained formulation in a fair learning application.
arXiv Detail & Related papers (2020-02-12T19:12:29Z)
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.