A Max-Plus Algebra Approach for Generating Non-Delay Schedule

Authors

  • Tena Žužek Faculty of Mechanical Engineering, University of Ljubljana
  • Aljoša Peperko Faculty of Mechanical Engineering, University of Ljubljana
  • Janez Kušar Faculty of Mechanical Engineering, University of Ljubljana

Abstract

Max-plus algebra is one of the promising mathematical approaches, that can be used for scheduling operations. It was already applied for Johnson’s algorithm and cyclic job shop problem. In this article, max-plus algebra is used for generating non-delay schedule. When using non-delay schedule approach, in each stage, task with earliest possible start is scheduled. If there is more than one task eligible for scheduling, we apply the priority (dispatching) rule, and in case of another tie, the tie-breaking rule is applied. We present simple step-by-step procedure for generating matrices of starting and finishing times of operations, using Max-plus algebra. We apply LRPT (Longest Remaining Processing Time) as priority rule and SPT (Shortest Processing Time) as tie-breaking rule.

Downloads

Published

2019-07-04

Issue

Volume 10 (2019), Number 1

Section

CRORR Journal Regular Issue

License

- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal

- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).