Optimal Task Scheduling · Green Banana

Green Banana Optimal Task Scheduler

Green Banana (GB) is an optimal task scheduler that finds optimal schedules for the task scheduling problem on homogeneous multi-processor systems with communication delays.

GB lets users choose from a suite of Mixed Integer Linear Programming (MILP) formulations to solve the scheduling problem with the CPLEX Optimisation Solver. Task execution times, precedence constraints, and communication delays are modelled with the Graph eXchange Language (GXL), a standard XML-based exchange format for graphs (see the GXL home page). Example input GXL and output GXL files are available; the expected input and output formats are documented.

Supported formulations

  • Transitivity Clause (TC) [1]
  • Revised Boolean Logic (RBL) [1]
  • SHD-BASIC, SHD-RELAXED, SHD-REDUCED [2]
  • Classic and Classic Compact [3]
  • Packing and Packing Compact [3]

Working with CPLEX log files

When a formulation is input to CPLEX, the default log file (cplex.log) appends on every run and is cumbersome to parse. Set a dedicated log file name with this sequence at the CPLEX prompt:

set logfile file_name.log
read file_name.lp
set timelimit 60      # seconds; max 10^75. Omit for an effectively unbounded limit
optimize
display solution variables -

Features

  • batchprocess — create a script to batch-process all .lp files with CPLEX. Run java gb -help for an example.
  • help — java gb -help shows what the suite supports, with instructions and examples.
  • gxlout — convert a CPLEX log file to GXL output, given the log and the input GXL.
  • printschedule — print the complete schedule to screen, given the log and the input GXL.

Download

Download the Green Banana optimal task scheduler from the Download page.

Graphs and results

Optimal schedules are in the Optimal Schedules database.

References

  1. Sarad Venugopalan and Oliver Sinnen. Optimal linear programming solutions for multiprocessor scheduling with communication delays. ICA3PP 2012, LNCS 7439, pp. 129–138. Springer. [Springer]
  2. Sarad Venugopalan and Oliver Sinnen. ILP formulations for Optimal Task Scheduling with Communication Delays on Parallel Systems. IEEE TPDS, 2014. DOI: 10.1109/TPDS.2014.2308175. [IEEE]
  3. T. Davidovic, L. Liberti, N. Maculan, and N. Mladenovic. Towards the Optimal Solution of the Multiprocessor Scheduling Problem with Communication Delays. MISTA 2007, pp. 128–135. [CiteSeerX]