Flow Shop Models and Constraint Graph Specifications

The Job Shop is a well-known model for scheduling problems, which are captured as a shop in which a set of jobs need to be completed that consist of operations that can be performed by machines of the shop. Operations take time and machines can only perform one operation at a time. This leads to a scheduling problem to decide what operation should be performed at what time, typically to complete all jobs as soon as possible. Different kinds of additional constraints may apply, such as ordering and dependencies between operations, deadlines or setup times for machines.

We have explored solutions to job shop (in particular flow shop) problems using constraint graph. A constraint graph is weighted graph structure in which vertices represent operations and weighted edges represent constraints between the start times of the operations it connects in a valid schedule. Scheduling decisions can be captured by adding edges to the graph. Longest path and positive cycle algorithms such as Bellman-Ford can be used to study schedulability and determine as-soon-as-possible schedules.

With the framework one can explore greedy list scheduling heuristics, backtracking branch-and-bound algorithms, or multi-objective heuristics.

Schedule methods have been applied to the xCPS system and in collaboration with Canon Production Printing to investigate scheduling of production printers.

Selected Publications

U. Waqas, M. Geilen, J. Kandelaars, L. Somers, T. Basten, S. Stuijk, P. Vestjens, and H. Corporaal, “A re-entrant flowshop heuristic for online scheduling of the paper path in a large scale printer,” in 2015 design, automation & test in europe conference & exhibition (date), 2015, pp. 573-578.
[Bibtex]

@INPROCEEDINGS{WGKea15,
author={Waqas, Umar and Geilen, Marc and Kandelaars, Jack and Somers, Lou and Basten, Twan and Stuijk, Sander and Vestjens, Patrick and Corporaal, Henk},
booktitle={2015 Design, Automation & Test in Europe Conference & Exhibition (DATE)},
title={A re-entrant flowshop heuristic for online scheduling of the paper path in a large scale printer},
year={2015},
volume={},
number={},
pages={573-578},
doi={10.7873/DATE.2015.0519}
}

J. van Pinxten, M. Geilen, T. Basten, U. Waqas, and L. Somers, “Online heuristic for the multi-objective generalized traveling salesman problem,” in 2016 design, automation & test in europe conference & exhibition (date), 2016, pp. 822-825.
[Bibtex]

@INPROCEEDINGS{PGBea16,
author={van Pinxten, Joost and Geilen, Marc and Basten, Twan and Waqas, Umar and Somers, Lou},
booktitle={2016 Design, Automation & Test in Europe Conference & Exhibition (DATE)},
title={Online heuristic for the Multi-Objective Generalized traveling salesman problem},
year={2016},
volume={},
number={},
pages={822-825},
doi={}
}

U. Waqas, M. Geilen, S. Stuijk, J. van Pinxten, T. Basten, L. Somers, and H. Corporaal, “A fast estimator of performance with respect to the design parameters of self re-entrant flowshops,” in 2016 euromicro conference on digital system design (dsd), 2016, pp. 215-221.
[Bibtex]

@INPROCEEDINGS{WGSea16,
author={Waqas, Umar and Geilen, Marc and Stuijk, Sander and van Pinxten, Joost and Basten, Twan and Somers, Lou and Corporaal, Henk},
booktitle={2016 Euromicro Conference on Digital System Design (DSD)},
title={A Fast Estimator of Performance with Respect to the Design Parameters of Self Re-Entrant Flowshops},
year={2016},
volume={},
number={},
pages={215-221},
doi={10.1109/DSD.2016.26}
}

U. Waqas, “Scheduling and variation-aware design of self-re-entrant flowshops,” PhD Thesis, 2017.
[Bibtex]

@phdthesis{Waq17,
title = "Scheduling and variation-aware design of self-re-entrant flowshops",
author = "U. Waqas",
note = "Proefschrift",
year = "2017",
month = nov,
day = "23",
language = "English",
isbn = "978-90-386-4372-4",
publisher = "Technische Universiteit Eindhoven",
school = "Electrical Engineering",
url = {https://research.tue.nl/en/publications/scheduling-and-variation-aware-design-of-self-re-entrant-flowshop},
}

J. V. Pinxten, U. Waqas, M. Geilen, T. Basten, and L. Somers, “Online scheduling of 2-re-entrant flexible manufacturing systems,” Acm trans. embed. comput. syst., vol. 16, iss. 5s, 2017.
[Bibtex]

@article{PWGea17,
author = {Pinxten, Joost Van and Waqas, Umar and Geilen, Marc and Basten, Twan and Somers, Lou},
title = {Online Scheduling of 2-Re-Entrant Flexible Manufacturing Systems},
year = {2017},
issue_date = {October 2017},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {16},
number = {5s},
issn = {1539-9087},
url = {https://doi.org/10.1145/3126551},
doi = {10.1145/3126551},
abstract = {Online scheduling of operations is essential to optimize productivity of flexible manufacturing systems (FMSs) where manufacturing requests arrive on the fly. An FMS processes products according to a particular flow through processing stations. This work focusses on online scheduling of re-entrant FMSs with flows using processing stations where products pass twice and with limited buffering between processing stations. This kind of FMS is modelled as a re-entrant flow shop with due dates and sequence-dependent set-up times. Such flow shops can benefit from minimization of the time penalties incurred from set-up times. On top of an existing greedy scheduling heuristic we apply a meta-heuristic that simultaneously explores several alternatives considering trade-offs between the used metrics by the scheduling heuristic. We identify invariants to efficiently remove many infeasible scheduling options so that the running time of online implementations is improved. The resulting algorithm is much faster than the state of the art and produces schedules with on average 4.6% shorter makespan.},
journal = {ACM Trans. Embed. Comput. Syst.},
month = {sep},
articleno = {160},
numpages = {20},
keywords = {flexible manufacturing systems, Re-entrant flow shops, bounded horizon scheduling}
}

@INPROCEEDINGS{PGBWS16,
author={van Pinxten, Joost and Geilen, Marc and Basten, Twan and Waqas, Umar and Somers, Lou},
booktitle={2016 Design, Automation & Test in Europe Conference & Exhibition (DATE)},
title={Online heuristic for the Multi-Objective Generalized traveling salesman problem},
year={2016},
volume={},
number={},
pages={822-825},
doi={}
}

J. van Pinxten, M. Geilen, M. Hendriks, and T. Basten, “Parametric critical path analysis for event networks with minimal and maximal time lags,” Ieee transactions on computer-aided design of integrated circuits and systems, vol. 37, iss. 11, pp. 2697-2708, 2018.
[Bibtex]

@ARTICLE{PGHB18,
author={van Pinxten, Joost and Geilen, Marc and Hendriks, Martijn and Basten, Twan},
journal={IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},
title={Parametric Critical Path Analysis for Event Networks With Minimal and Maximal Time Lags},
year={2018},
volume={37},
number={11},
pages={2697-2708},
doi={10.1109/TCAD.2018.2857360}
}

J. V. Pinxten, M. Geilen, and T. Basten, “Parametric scheduler characterization,” Acm trans. embed. comput. syst., vol. 18, iss. 5s, 2019.
[Bibtex]

@article{PGB19,
author = {Pinxten, Joost Van and Geilen, Marc and Basten, Twan},
title = {Parametric Scheduler Characterization},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {18},
number = {5s},
issn = {1539-9087},
url = {https://doi.org/10.1145/3358226},
doi = {10.1145/3358226},
journal = {ACM Trans. Embed. Comput. Syst.},
month = {oct},
articleno = {110},
numpages = {25},
keywords = {re-entrant flexible manufacturing system, system design, Real time scheduling}
}

J. H. H. van Pinxten, “Optimization of product flows in flexible manufacturing systems,” PhD Thesis, 2018.
[Bibtex]

@phdthesis{Pin18,
title = "Optimization of product flows in flexible manufacturing systems",
abstract = "Efficient merging of streams of sheets in industrial printers",
author = "van Pinxten, J.H.H.",
note = "Proefschrift",
year = "2018",
month = dec,
day = "20",
language = "English",
isbn = "978-94-6380-165-2",
publisher = "Technische Universiteit Eindhoven",
school = "Electrical Engineering",
url={https://research.tue.nl/en/publications/optimization-of-product-flows-in-flexible-manufacturing-systems},
}

R. van der Tempel, J. van Pinxten, M. Geilen, and U. Waqas, “A heuristic for variable re-entrant scheduling problems,” in 2018 21st euromicro conference on digital system design (dsd), 2018, pp. 336-341.
[Bibtex]

@INPROCEEDINGS{TPGW18,
author={van der Tempel, Roel and van Pinxten, Joost and Geilen, Marc and Waqas, Umar},
booktitle={2018 21st Euromicro Conference on Digital System Design (DSD)},
title={A Heuristic for Variable Re-Entrant Scheduling Problems},
year={2018},
volume={},
number={},
pages={336-341},
doi={10.1109/DSD.2018.00065}
}