Counting and enumerating feasible rotating schedules by means of Gröbner bases

Raúl Falcón; Eva Barrena; David Canca; Gilbert Laporte

doi:10.1016/j.matcom.2014.12.002

Counting and enumerating feasible rotating schedules by means of Gröbner bases

Raúl Falcón, Eva Barrena, David Canca, Gilbert Laporte

Research output: Contribution to journal › Article › peer-review

7 Citations (SciVal)

Abstract

This paper deals with the problem of designing and analyzing rotating schedules with an algebraic computational approach. Specifically, we determine a set of Boolean polynomials whose zeros can be uniquely identified with the set of rotating schedules related to a given workload matrix subject to standard constraints. These polynomials constitute zero-dimensional radical ideals, whose reduced Gröbner bases can be computed to count and even enumerate the set of rotating schedules that satisfy the desired set of constraints. Thereby, it enables to analyze the influence of each constraint in the same.

Original language	English
Pages (from-to)	139-151
Number of pages	13
Journal	Mathematics and Computers in Simulation
Volume	125
DOIs	https://doi.org/10.1016/j.matcom.2014.12.002
Publication status	Published - Jul 2016

Keywords

Boolean ideal
Gröbner basis
Rotating schedule

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science
Numerical Analysis
Modelling and Simulation
Applied Mathematics

Access to Document

10.1016/j.matcom.2014.12.002

Cite this

@article{d50df51cafea4de6b9d525164873e573,

title = "Counting and enumerating feasible rotating schedules by means of Gr{\"o}bner bases",

abstract = "This paper deals with the problem of designing and analyzing rotating schedules with an algebraic computational approach. Specifically, we determine a set of Boolean polynomials whose zeros can be uniquely identified with the set of rotating schedules related to a given workload matrix subject to standard constraints. These polynomials constitute zero-dimensional radical ideals, whose reduced Gr{\"o}bner bases can be computed to count and even enumerate the set of rotating schedules that satisfy the desired set of constraints. Thereby, it enables to analyze the influence of each constraint in the same.",

keywords = "Boolean ideal, Gr{\"o}bner basis, Rotating schedule",

author = "Ra{\'u}l Falc{\'o}n and Eva Barrena and David Canca and Gilbert Laporte",

year = "2016",

month = jul,

doi = "10.1016/j.matcom.2014.12.002",

language = "English",

volume = "125",

pages = "139--151",

journal = "Mathematics and Computers in Simulation",

issn = "0378-4754",

publisher = "Elsevier",

}

TY - JOUR

T1 - Counting and enumerating feasible rotating schedules by means of Gröbner bases

AU - Falcón, Raúl

AU - Barrena, Eva

AU - Canca, David

AU - Laporte, Gilbert

PY - 2016/7

Y1 - 2016/7

N2 - This paper deals with the problem of designing and analyzing rotating schedules with an algebraic computational approach. Specifically, we determine a set of Boolean polynomials whose zeros can be uniquely identified with the set of rotating schedules related to a given workload matrix subject to standard constraints. These polynomials constitute zero-dimensional radical ideals, whose reduced Gröbner bases can be computed to count and even enumerate the set of rotating schedules that satisfy the desired set of constraints. Thereby, it enables to analyze the influence of each constraint in the same.

AB - This paper deals with the problem of designing and analyzing rotating schedules with an algebraic computational approach. Specifically, we determine a set of Boolean polynomials whose zeros can be uniquely identified with the set of rotating schedules related to a given workload matrix subject to standard constraints. These polynomials constitute zero-dimensional radical ideals, whose reduced Gröbner bases can be computed to count and even enumerate the set of rotating schedules that satisfy the desired set of constraints. Thereby, it enables to analyze the influence of each constraint in the same.

KW - Boolean ideal

KW - Gröbner basis

KW - Rotating schedule

UR - http://www.scopus.com/inward/record.url?scp=84922116304&partnerID=8YFLogxK

U2 - 10.1016/j.matcom.2014.12.002

DO - 10.1016/j.matcom.2014.12.002

M3 - Article

AN - SCOPUS:84922116304

SN - 0378-4754

VL - 125

SP - 139

EP - 151

JO - Mathematics and Computers in Simulation

JF - Mathematics and Computers in Simulation

ER -

Counting and enumerating feasible rotating schedules by means of Gröbner bases

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this