Heuristics for scheduling tasks in a job-shop

The scheduling of operations in industrial environment is often modelled as a job-shop problem. However, for this type of problem there are no efficient algorithms to obtain the optimal solution, unless the shop has only one or two machines. The absence of optimization tools often leads to the use of heuristics in the search of the problem solution. In this paper two new heuristics are presented for the generation of schedules. Both heuristics aim to minimize the largest tardiness, and allow the user to define the sequencing of the operations processed in bottleneck machines. The heuristics automatically schedule all the other operations. The job-shop problem is decomposed in single machine scheduling problems, which are solved by the Cartier algorithm or by the Schrage heuristic. Tests performed on 100 problems and in a pilot industrial company demonstrated that the proposed heuristics provide good schedules and flexibility, and can substitute with success the manual and time consuming processes that are still used for scheduling industrial operations.