Original scientific paper

https://doi.org/10.17535/crorr.2019.0004

A Max-Plus algebra approach for generating a non-delay schedule

Tena Žužek orcid.org/0000-0003-3389-0110 ; Faculty of Mechanical Engineering, University of Ljubljana, Ljubljana, Slovenia
Aljoša Peperko orcid.org/0000-0002-8547-0057 ; Faculty of Mechanical Engineering, University of Ljubljana, Ljubljana, Slovenia
Janez Kušar ; Faculty of Mechanical Engineering, University of Ljubljana, Ljubljana, Slovenia

Abstract

A Max-Plus algebra is one of the promising mathematical approaches that can be used for scheduling operations. It was already applied for the presentation of Johnson’s algorithm and for solving cyclic jobshop problems, but it had not yet been applied for non-delay schedules. In this article, max-plus algebra is used to formally present the generation of a non-delay schedule for the first time. We present a simple algorithm for generating matrices of starting and finishing times of operations, using max-plus algebra formalism. We apply the LRPT (Longest Remaining Processing Time) rule as the priority rule, and the SPT (Shortest Processing Time) rule as the tie-breaking rule. The algorithm is applicable for any other pair of priority rules with a few minor adjustments.

Keywords

Max-Plus algebra; non-delay schedule; priority rules; project scheduling

Hrčak ID:

222082

URI

https://hrcak.srce.hr/222082

Publication date:

4.7.2019.

Visits: 1.190 *