Tacking complex job shop problems using operation based scheduling

摘要

Scheduling is a combinatorial problem with important impact on both industry and commerce. If it is performed well it yields time and efficiency benefits and hence reduces costs. Genetic Algorithms have been applied to solve several types ofscheduling problems; Flow Shop, Resource, Staff and Line Balancing have all been tackled. However Job-shop Scheduling is the most common problem of interest. The Job-shop Scheduling Problem (JSP) involves placing jobs onto a set of machines with the aimof minimising makespan, the total time to complete all jobs. The standard JSP model is relatively simple and cannot cope with many real world situations. This paper outlines a new method, using an operation based construction, which expands the JSP toincrease its functionality and applicability. This allows for much more complex job shop problems involving flexible machines, setup and maintenance times, deadlines and multiple optimisation criteria. The method is fully explained and demonstrated usinga 20 job-4 machine example.