Scheduling in Manufacturing Systems: The Ant Colony Approach

Read this section. It makes the case that production systems are similar to ant colonies because ants continue to learn from one another and find ways to become more efficient at their task at hand. As you read, pay special attention to some of the scheduling problems.

1. Introduction

Scheduling problems, also in manufacturing systems, are described by following parameters: the processing – computing – environments comprising processor (machines) set, other resources comprising transportations and executions devices, processes (tasks) set, and optimality criterion. We assume that processor set consists of m elements. Two classes of processors can be distinguished: dedicated (specialized) processors and parallel processors.

In production systems machines are regarded as dedicated rather than as parallel. In such a case we distinguish three types of dedicated processor systems: flow-shop, open-shop, and job-shop. In the flow-shop all tasks have the same number of operations which are performed sequentially and require the same sets of processors. In the open-shop the order among the operations is immaterial. For the job-shop, the sequence of operations and the sets of required processors are defined for each process separately.

In the case of parallel processors each processor can execute any task. Hence, a task requires some number of arbitrary processors. As in deterministic scheduling theory parallel processors are divided into three classes: identical processors – provided that all tasks are executed on all processors with that same productivity, uniform processors – if the productivity depends on the processor and on the task, and unrelated processors – for which execution speed depends on the processor and on the task. In each of the above cases productivity of the processor can be determined.

Apart from the processors the can be also a set of additional resources, each available in m i units.

The second parameter of the scheduling problem is the tasks system. The tasks correspond to the applications for manufactured goods. We assume that the set of tasks consists of n tasks. For the whole tasks system it is possible to determine such feature as preemptability (or nonpreemptability) and existence (or nonexistence) of precedence constraints.

Precedence constraints are represented as directed acyclic graphs (DAGs). Each task separately is described by a number of parameters. We enumerate them in the following:

  • Number of operations,
  • Execution time,
  • Ready time,
  • Deadline,
  • Resources requirements,
  • Weight.

The optimality criteria constituting the third element of the scheduling problem are:

  • Schedule length,
  • Maximum lateness,
  • Mean flow time,
  • Mean tardiness.

Due to the fact that scheduling problems and their optimizations are general NP-complete we suggest meta-heuristic approach: Ant Colony Optimization and its comparison with neural method and with polynomial algorithms for certain exemplary problems of task scheduling.

If a heuristic algorithm (such as ACO) finds an optimal solution to polynomial problems, it is probable that solutions found for NP-complete problems will also be optimal or least approximated to optimal. ACO algorithm was tested with known polynomial algorithms and all of them achieved optimal solutions for those problems.

The comparisons utilized such polynomial algorithms as:

  • Coffman-Graham Algorithm,
  • Hu Algorithm,
  • Baer Algorithm,

For non-polynomial problems of tasks scheduling ACO algorithm was tested with list algorithms (HLFET, HLFNET, SCFET, SCFNET), with PDF/HIS for STG tasks and neural approach.


Source: Mieczysław Drabowski and Edward Wantuch , https://www.intechopen.com/chapters/39584
Creative Commons License This work is licensed under a Creative Commons Attribution 3.0 License.