Scheduling of manufacturing systems under dual-resource constraints using genetic algorithms

Scheduling belongs to the special class of NP-hard problems for which no polynomial time algorithm has been found. Therefore, a schedule that is the best possible near-optimal solution is often acceptable. This paper presents a scheduling approach, based on Genetic Algorithms (GAs), developed to address the scheduling problem in manufacturing systems constrained by both machines and workers. This genetic algorithm utilizes a new chromosome representation, which takes into account machine and worker assignments to jobs. A set of experiments for determining the best staffing level and machine and worker assignment to jobs was performed. A study was conducted using dispatching rules with various performance measures for two types of shop characteristics: (i) dual-resource (machines and workers) constrained, and (ii) single-resource constrained (machines only). An example is used for illustration and comparison. The resulting scheduling methodology is capable of determining the best staffing level and dispatching rules for the chosen performance measure in both single and dual-resource constrained shops. Decisions to adopt the prescribed staffing strategy to improve the primary performance measures such as mean flow time, mean tardiness, and mean waiting time must be balanced by managers against the potential increase in direct cost. The developed scheduling approach and formulation proved to be very useful for optimizing production performance under the realistic conditions imposed by both machine and worker availability constraints. Such a tool should be used to define a priori the best dispatching rules and schedules for a given set of production requirements and objectives.