Green Banana (GB for short) optimal task scheduler aims at finding optimal schedules for the task scheduling problem on homogeneous
multi-processor systems with communication delays.

GB is designed for users to choose from a suite of Mixed Integer Linear Programming (MILP) formulations to solve the scheduling
problem with CPLEX Optimisation Solver.

The task's execution times, the precedence constraints between tasks and communication delays are conveniently modelled with the Graph eXchange
Language (GXL) that is designed to be a standard exchange format for graphs. More information may be found on the
GXL Home Page. Example of an input GXL file can be found
here
and the corresponding output GXL file with the full schedule
here. If the input GXL file starts with a node
number of 0, the output GXL files have 1 added to every node number in-order to maintian numbering consistency.
The expected input and output GXL file formats used are found
here and
here.

The GB scheduler suite supports the following formulation and features:

- Formulation:
**Transitivity Clause (TC)**as in [1].

- Formulation:
**Revised Boolean Logic (RBL)**as in [1]. - Formulation:
**SHD-BASIC**as in [2]. - Formulation:
**SHD-RELAXED**as in [2]. - Formulation:
**SHD-REDUCED**as in [2]. - Formulation:
**Classic**as in [3]. Linearisation using Eq. 9-11 in [3]. - Formulation:
**Classic Compact**as in [3]. Linearisation using Eq. 12-13 in [3]. - Formulation:
**Packing**as in [3]. Linearisation using Eq. 31 in [3]. - Formulation:
**Packing Compact**as in [3]. Linearisation using Eq. 32-33 in [3]. - When the LP formulation is input to CPLEX, CPLEX uses a default log file (cplex.log). However, every time CPLEX executes, the default log file appends and is cumbersome to parse and using the default log file is to be avoided. It is possible to set CPLEX to have a desired log file name and the following sequence of commands are recommended. List of commands to be input at the CPLEX prompt:
- Set logfile file_name.log
- read file_name.lp
- set timelimit 60 [i.e timelimit of 60 seconds, the maximum timelimit being 10^75 seconds]. If this step is omitted, an (practically) un-bounded timelimit is chosen.
- optimize
- display solution variables -
- Set logfile tc_2p_gb_intree.log
- read tc_2p_gb_intree.lp
- set timelimit 60
- optimize
- display solution variables -
- Set logfile rbl_2p_intree.log
- read rbl_2p_intree.lp
- set timelimit 60
- optimize
- display solution variables -

Two examples are given below

- Feature
**batchprocess:**This feature can be used to create a script to batch process all the .lp extension files with CPLEX. This essentially appends to batch script file the sequence of steps seen in Example 1 and Example 2, given the lp filename and the timelimit. When the GB scheduler is downloaded, type java gb -help to see an example on how this works. - Feature
**help:**After downloading the GB scheduler, type java gb -help to see what the Green Banana suite supports, instructions and examples on how to use it. - Feature
**gxlout:**This feature allows the user to convert the CPLEX log file to GXL output format, given the CPLEX log file and the input GXL file. To see an example, type java gb -help - Feature
**printschedule:**This feature prints on screen the complete schedule, given the CPLEX log file and the input GXL file. To see an example, type java gb - help

[3]. Sarad Venugopalan and Oliver Sinnen.

[3]. T. Davidovic, L. Liberti, N. Maculan, and N. Mladenovic. Towards the Optimal solution of the Multiprocessor Scheduling Problem with Communication Delays. In 3rd Multidisciplinary International Conference on Scheduling: Theory and Application., pages 128–135, 2007. [CiteSeerX Abstract] .