Scheduling of jobs on parallel machines using genetic algorithms.

摘要

Machines in parallel is a setup that widely exists in industrial situations. The problem of scheduling a set of jobs on parallel machines is addressed in previous literature and found to be NP-hard for most of its cases. Past and recent research that addressed this problem did not take into account the existence of significant setup times. Rather the problem is solved under the assumption that setup times are negligible and can therefore be neglected. Neglecting setup times, even though not practical and can produce invalid schedules, reduces the problem complexity and hence it becomes easier to solve. Another aspect of the problem, that was not covered in the past research, is considering more than one criterion. It is logical to consider more than one criterion in many practical situations. For example, considering a criterion that reflects customer satisfaction such as due date, and in the mean time considering a criterion that reflects the status of the shop such as makespan or flow time. These two categories of criteria are conflicting in nature. Therefore, solving the scheduling problem so that a compromise between these criteria is achieved may become attractive.; In this work, the problem of scheduling jobs on a set of parallel machines taking into consideration significant setup times was studied. Genetic algorithms (GA) was used as solution tool mainly because almost all of the cases considered are NP-hard and the size of the problem instances was considerably large. Typical scheduling problems were solved considering five criteria. First each criterion was considered separately, then each problem was solved using bicriteria approach. Some of the GA results were compared to previously published problem instances and found that GA resulted in the optimal solutions in shorter time and less number of generations.; The same set of single objective problem was solved using an heuristic technique. The advantages of using heuristics for large combinatorial problems are evident even though the quality of the solutions may deteriorate. The results obtained by the heuristic were compared to those obtained by the GA. In most cases, it was found that these solutions are higher than those obtained from the GA by 5% to 20%.; The GA was extended in order to solve parallel machines scheduling problem for the bicriteria case. The bicriteria combinations were selected based on previous literature and also to reflect conflicting objectives. The problems used for the bicriteria situations were the same as those used for the single criteria cases. Results obtained in this study indicated that accepting a little deterioration in the main criterion would dramatically improve the value of the other objective.