Green Banana Optimal Task Scheduler

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 -

    Two examples are given below

    Example 1

    • Set logfile tc_2p_gb_intree.log
    • read tc_2p_gb_intree.lp
    • set timelimit 60
    • optimize
    • display solution variables -

    Example 2

    • Set logfile rbl_2p_intree.log
    • read rbl_2p_intree.lp
    • set timelimit 60
    • optimize
    • display solution variables -

  • 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

Download

        Download the Green Banana optimal task scheduler from here.

Graphs and Results

        Graphs and optimal schedules are found here.

Reference

[1]. Sarad Venugopalan and Oliver Sinnen. Optimal linear programming solutions for multiprocessor scheduling with communication delays.12th International Conference, ICA3PP 2012. In Yang Xiang, Ivan Stojmenovic, BernadyO. Apduhan, Guojun Wang, Koji Nakano, and Albert Zomaya, editors, Algorithms and Architectures for Parallel Processing, volume 7439 of Lecture Notes in Computer Science, pages 129–138. Springer Berlin Heidelberg, 2012. [Springer Abstract] .

[3]. Sarad Venugopalan and Oliver Sinnen. ILP formulations for Optimal Task Scheduling with Communication Delays on Parallel Systems, IEEE Transactions on Parallel and Distributed Systems. Accepted 1st February 2014.DOI: 10.1109/TPDS.2014.2308175 [IEEE TPDS Early Access] .

[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] .