Scheduling problems

DOI10.1016/J.JCTA.2015.11.001zbMATH1328.05190OpenAlexW2911755786MaRDI QIDQ899491FDOQ899491

Authors Felix Breuer, Caroline Klivans

Publication date 28 December 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2978

zbMATH Keywords

schedulinghyperplane arrangementsEhrhart theoryquasisymmetric functions\(h\)-vectors

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Symmetric functions and generalizations (05E05)

Abstract: We introduce the notion of a scheduling problem which is a boolean function $S$ over atomic formulas of the form $x_{i}leq{x}_j$. Considering the $x_i$ as jobs to be performed, an integer assignment satisfying $S$ schedules the jobs subject to the constraints of the atomic formulas. The scheduling counting function counts the number of solutions to $S$. We prove that this counting function is a polynomial in the number of time slots allowed. Scheduling polynomials include the chromatic polynomial of a graph, the zeta polynomial of a lattice, the Billera-Jia-Reiner polynomial of a matroid. To any scheduling problem, we associate not only a counting function for solutions, but also a quasisymmetric function and a quasisymmetric function in non-commuting variables. These scheduling functions include the chromatic symmetric functions of Sagan, Gebhard, and Stanley, and a close variant of Ehrenborg's quasisymmetric function for posets. Geometrically, we consider the space of all solutions to a given scheduling problem. We extend a result of Steingr'immson by proving that the $h$-vector of the space of solutions is given by a shift of the scheduling polynomial. Furthermore, under certain niceness conditions on the defining boolean function, we prove partitionability of the space of solutions and positivity of fundamental expansions of the scheduling quasisymmetric functions and of the $h$-vector of the scheduling polynomial.

Recommendations

• scientific article; zbMATH DE number 7203465
• scientific article; zbMATH DE number 781250
• The counting complexity of a simple scheduling problem
• Plurigraph coloring and scheduling problems
• Optimal scheduling combinatorics

Cites work

• scientific article; zbMATH DE number 1827070 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• scientific article; zbMATH DE number 3895079 (Why is no real title available?)
• A chromatic symmetric function in noncommuting variables
• A quasisymmetric function for matroids
• A symmetric function generalization of the chromatic polynomial of a graph
• Bounds on the coefficients of tension and flow polynomials
• Coloring complexes and arrangements
• Combinatorial reciprocity theorems
• Ehrhart \(f^*\)-coefficients of polytopal complexes are non-negative integers
• Hypergraph coloring complexes
• Inside-out polytopes
• Lectures on Polytopes
• On posets and Hopf algebras
• Ordered structures and partitions
• Shellable Decompositions of Cells and Spheres.
• THE HOPF ALGEBRAS OF SYMMETRIC FUNCTIONS AND QUASI-SYMMETRIC FUNCTIONS IN NON-COMMUTATIVE VARIABLES ARE FREE AND CO-FREE
• The Bergman complex of a matroid and phylogenetic trees
• The coloring ideal and coloring complex of a graph
• Triangulations. Structures for algorithms and applications
• Viewing counting polynomials as Hilbert functions via Ehrhart theory

Cited in

(25)

• Rescheduling problems with allowing for the unexpected new jobs arrival
• Reallocation problems in scheduling
• Scheduling with target start times
• scientific article; zbMATH DE number 5039509 (Why is no real title available?)
• scientific article; zbMATH DE number 7203465 (Why is no real title available?)
• Scheduling Problems in Cross Docking
• scientific article; zbMATH DE number 1323827 (Why is no real title available?)
• On scheduling with ready-times, due-dates and vacations
• Möbius inversion as duality for Hopf monoids
• scientific article; zbMATH DE number 1487903 (Why is no real title available?)
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs
• Scheduling to Maximize Participation
• Plurigraph coloring and scheduling problems
• Quasisymmetric and Schur expansions of cycle index polynomials
• Structured solutions in scheduling problems
• scientific article; zbMATH DE number 3941253 (Why is no real title available?)
• scientific article; zbMATH DE number 3978803 (Why is no real title available?)
• New invariants for permutations, orders and graphs
• Scheduler -- a system for staff planning
• Algorithms and Data Structures
• Scheduling to maximize participation
• Hopf Monoids and Generalized Permutahedra
• Chromatic symmetric functions of hypertrees
• Complex Scheduling
• Tree expansions of some Lie idempotents

This page was built for publication: Scheduling problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899491)