A max-plus algebra approach for generating a non-delay schedule

Žužek, Tena (author), Peperko, Aljoša (author), Kušar, Janez (author)

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.

• Language: English
• Keywords: max-plus algebra, non-delay schedules, priority rules, project schedulling
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FS - Faculty of Mechanical Engineering
• Publication status: Published
• Publication version: Version of Record
• Year: 2019
• Number of pages: Str. 35-44
• Numbering: Vol. 10, no. 1
• PID: 20.500.12556/RUL-108522
• UDC: 658.5(045)
• ISSN on article: 1848-0225
• DOI: 10.17535/crorr.2019.0004
• COBISS.SI-ID: 16696091
• Publication date in RUL: 05.07.2019

Record is a part of a journal

• Title: Croatian operational research review : CRORR
• Publisher: Croatian Operational Research Society
• ISSN: 1848-0225
• COBISS.SI-ID: 10670108

Secondary language

• Language: Slovenian
• Keywords: max-plus algebra, non-delay urniki, prioritetna pravilla, časovni načrti projektov

Projects

• Funder: ARRS - Slovenian Research Agency
• Project number: P2-0270, P1-0222, J1-8133
• Name: Proizvodni sistemi, laserske tehnologije in spajanje materialov; Algebra v teoriji operatorjev in finančna matematika; Preslikave na matrikah in operatorjih