Scheduling problems

DOI10.1016/J.JCTA.2015.11.001MaRDI QIDQ899491zbMATH OpenOpenAlexFDO

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

\(h\)-vectorsEhrhart theoryhyperplane arrangementsquasisymmetric functionsscheduling

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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 Bergman complex of a matroid and phylogenetic trees
• The coloring ideal and coloring complex of a graph
• THE HOPF ALGEBRAS OF SYMMETRIC FUNCTIONS AND QUASI-SYMMETRIC FUNCTIONS IN NON-COMMUTATIVE VARIABLES ARE FREE AND CO-FREE
• Triangulations. Structures for algorithms and applications
• Viewing counting polynomials as Hilbert functions via Ehrhart theory

Cited in

(25)

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

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)