Scheduling problems

DOI10.1016/J.JCTA.2015.11.001zbMATH Open1328.05190arXiv1401.2978OpenAlexW2911755786MaRDI QIDQ899491FDOQ899491

Felix Breuer, Caroline Klivans

Publication date: 28 December 2015

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A symmetric function generalization of the chromatic polynomial of a graph
• Lectures on Polytopes
• Triangulations. Structures for algorithms and applications
• The Bergman complex of a matroid and phylogenetic trees
• Bounds on the coefficients of tension and flow polynomials
• Inside-out polytopes
• A chromatic symmetric function in noncommuting variables
• On posets and Hopf algebras
• 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
• Ordered structures and partitions
• Hypergraph coloring complexes
• Coloring complexes and arrangements
• The coloring ideal and coloring complex of a graph
• Viewing counting polynomials as Hilbert functions via Ehrhart theory
• Combinatorial reciprocity theorems
• A quasisymmetric function for matroids
• Ehrhart \(f^*\)-coefficients of polytopal complexes are non-negative integers

Cited In (25)

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

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)