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

  • 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.

Published
2019-07-04
Section
CRORR Journal Regular Issue