Advance Algorithm for Scheduling Problems: Johnson's with Heuristic’s Procedure

The job-shop problem of scheduling n≥2 jobs in m≥2 machines is a non-polynomial (NP) hard problem with no general method. Multiple machine scheduling problems are challenging due to the complexity arising from finding an optimal sequence of jobs in the face of several and sometimes, conflicting criteria functions. In this work we modified the Johnson’s algorithm, creating a new heuristic algorithm, which schedules n-jobs (n≥2) in multiple machines (n≥3) directly without conversion to a two-machine problem. The numerical illustration results obtained from the heuristic algorithm for the multiple machine scheduling problems are compared with solution from the Palmer’s heuristic and found to produce better results for makes-span and idle times. Other heuristics can be modified and compared with results found in this work.