DEVELOPMENT OF GENETIC ALGORITHM-BASED METHODOLOGY FOR SCHEDULING OF MOBILE ROBOTS

Vinh Quang Dang

Research output: PhD thesis

1359 Downloads (Pure)

Abstract

This thesis addresses the issues of scheduling of mobile robot(s) at operational levels of
manufacturing systems. More specifically, two problems of scheduling of a single
mobile robot with part-feeding tasks and scheduling of multiple mobile robots with
preemptive tasks are taken into account. For the first scheduling problem, a single
mobile robot is considered to collect and transport container of parts and empty them
into machine feeders where needed. A limit on carrying capacity of the single mobile
robot and hard time windows of part-feeding tasks are considered. The objective of the
first problem is to minimize the total traveling time of the single mobile robot and
thereby increase its availability. For the second scheduling problem, a fleet of mobile
robots is considered together with a set of machines to carry out different types of tasks,
e.g. pre-assembly or quality inspection. Some of the tasks are non-preemptive while the
others are preemptive. The considered mobile robots have capabilities to not only
transport non-preemptive tasks between some machines but also process preemptive
tasks on other machines. These mobile robots are allowed to interrupt their preemptive
tasks to carry out transportation of non-preemptive tasks when needed. The objective of
the second problem is to minimize the time required to complete all tasks while taking
account of precedence constraints.
To deal with each mentioned scheduling problem, each mathematical model is
first formulated. This allows describing each problem and finding optimal solutions for
each one. However, the formulated mathematical models could only be applicable to
small-scale problems in practice due to the significant increase of computation time as
the problem size grows. Note that making schedules of mobile robots is part of real-time
operations of production managers. Hence to deal with large-scale applications, each
heuristic based on genetic algorithms is then developed to find near-optimal solutions
within a reasonable computation time for each problem. The quality of these solutions is
then compared and evaluated by using the solutions of the mathematical models as
reference points. The results from numerical experiments in this thesis show that the
proposed heuristics are capable of solving problems of various sizes and more efficient
than the mathematical models in terms of the objective values when giving the same
limited computation time. The research results are useful for production managers to
make decisions at operational levels and the proposed heuristics could be also applied to
a variety of tasks of not only mobile robots but also automatic guided vehicles.
Original languageEnglish
Publisher
Print ISBNs87-91200-64-4
Publication statusPublished - 2014

Cite this