Two Jobs and M-Machine Problems

by

The good news is that for two jobs and M machines (where M is any number greater than or equal to 2), the scheduling problem can still be solved relatively easily using a graphical method. This approach doesn’t require complex algorithms like Branch and Bound and provides an optimal solution.

Here’s how the graphical method works:

  1. Processing Time Table: Start by creating a table that shows the processing times for each job (Job 1 and Job 2) on each of the M machines (Machine 1, Machine 2, …, Machine M).

  2. Gantt Chart Representation: Next, imagine a Gantt chart with two axes:

    • The X-axis represents time.
    • The Y-axis represents the M machines.

  3. Rectangular Blocks: For each machine, create a rectangular block on the Gantt chart. The block’s width represents the processing time for that specific job on that machine. Stack these rectangles vertically, one on top of the other, for each machine.

  4. Connecting the Blocks: Now comes the key step: connect the corresponding rectangles for Job 1 and Job 2 across different machines. Remember, only one job can be processed on a machine at a time.

  5. Diagonal Lines: Since both jobs cannot be processed simultaneously on the same machine, the connections cannot form diagonal lines within the rectangle blocks. They can only connect horizontally across rectangles or vertically along the same machine.

  6. Minimum Idle Time Path: Identify the path from the origin (bottom left corner) to the “Finish” point (top right corner) that minimizes the total horizontal and vertical movement. This path represents the optimal job sequence that minimizes idle time for both jobs.

Benefits:

  • This graphical method is easy to visualize and understand.
  • It is guaranteed to find the optimal solution for two jobs and M machines.

Additional Notes:

  • The total completion time for each job can be calculated by adding the processing time for that job on each machine to the idle time observed in the optimal path on the Gantt chart.
  • This method assumes no setup times between jobs and that processing times are known beforehand.

While Johnson’s Algorithm doesn’t directly apply here, the underlying principle of minimizing idle time remains crucial. The graphical approach achieves this by visually identifying the sequence that keeps both machines working as much as possible.