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

Vinh Quang Dang

Publikation: Bog/antologi/afhandling/rapportPh.d.-afhandlingForskning

1225 Downloads (Pure)

Resumé

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.
OriginalsprogEngelsk
ForlagInstitut for Mekanik og Produktion, Aalborg Universitet
Antal sider208
ISBN (Trykt)87-91200-64-4
StatusUdgivet - 2014

Citer dette

Dang, V. Q. (2014). DEVELOPMENT OF GENETIC ALGORITHM-BASED METHODOLOGY FOR SCHEDULING OF MOBILE ROBOTS. Institut for Mekanik og Produktion, Aalborg Universitet.
Dang, Vinh Quang. / DEVELOPMENT OF GENETIC ALGORITHM-BASED METHODOLOGY FOR SCHEDULING OF MOBILE ROBOTS. Institut for Mekanik og Produktion, Aalborg Universitet, 2014. 208 s.
@phdthesis{f27f2a1081b74001a382920add1e5c1a,
title = "DEVELOPMENT OF GENETIC ALGORITHM-BASED METHODOLOGY FOR SCHEDULING OF MOBILE ROBOTS",
abstract = "This thesis addresses the issues of scheduling of mobile robot(s) at operational levels ofmanufacturing systems. More specifically, two problems of scheduling of a singlemobile robot with part-feeding tasks and scheduling of multiple mobile robots withpreemptive tasks are taken into account. For the first scheduling problem, a singlemobile robot is considered to collect and transport container of parts and empty theminto machine feeders where needed. A limit on carrying capacity of the single mobilerobot and hard time windows of part-feeding tasks are considered. The objective of thefirst problem is to minimize the total traveling time of the single mobile robot andthereby increase its availability. For the second scheduling problem, a fleet of mobilerobots 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 theothers are preemptive. The considered mobile robots have capabilities to not onlytransport non-preemptive tasks between some machines but also process preemptivetasks on other machines. These mobile robots are allowed to interrupt their preemptivetasks to carry out transportation of non-preemptive tasks when needed. The objective ofthe second problem is to minimize the time required to complete all tasks while takingaccount of precedence constraints.To deal with each mentioned scheduling problem, each mathematical model isfirst formulated. This allows describing each problem and finding optimal solutions foreach one. However, the formulated mathematical models could only be applicable tosmall-scale problems in practice due to the significant increase of computation time asthe problem size grows. Note that making schedules of mobile robots is part of real-timeoperations of production managers. Hence to deal with large-scale applications, eachheuristic based on genetic algorithms is then developed to find near-optimal solutionswithin a reasonable computation time for each problem. The quality of these solutions isthen compared and evaluated by using the solutions of the mathematical models asreference points. The results from numerical experiments in this thesis show that theproposed heuristics are capable of solving problems of various sizes and more efficientthan the mathematical models in terms of the objective values when giving the samelimited computation time. The research results are useful for production managers tomake decisions at operational levels and the proposed heuristics could be also applied toa variety of tasks of not only mobile robots but also automatic guided vehicles.",
author = "Dang, {Vinh Quang}",
year = "2014",
language = "English",
isbn = "87-91200-64-4",
publisher = "Institut for Mekanik og Produktion, Aalborg Universitet",

}

Dang, VQ 2014, DEVELOPMENT OF GENETIC ALGORITHM-BASED METHODOLOGY FOR SCHEDULING OF MOBILE ROBOTS. Institut for Mekanik og Produktion, Aalborg Universitet.

DEVELOPMENT OF GENETIC ALGORITHM-BASED METHODOLOGY FOR SCHEDULING OF MOBILE ROBOTS. / Dang, Vinh Quang.

Institut for Mekanik og Produktion, Aalborg Universitet, 2014. 208 s.

Publikation: Bog/antologi/afhandling/rapportPh.d.-afhandlingForskning

TY - BOOK

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

AU - Dang, Vinh Quang

PY - 2014

Y1 - 2014

N2 - This thesis addresses the issues of scheduling of mobile robot(s) at operational levels ofmanufacturing systems. More specifically, two problems of scheduling of a singlemobile robot with part-feeding tasks and scheduling of multiple mobile robots withpreemptive tasks are taken into account. For the first scheduling problem, a singlemobile robot is considered to collect and transport container of parts and empty theminto machine feeders where needed. A limit on carrying capacity of the single mobilerobot and hard time windows of part-feeding tasks are considered. The objective of thefirst problem is to minimize the total traveling time of the single mobile robot andthereby increase its availability. For the second scheduling problem, a fleet of mobilerobots 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 theothers are preemptive. The considered mobile robots have capabilities to not onlytransport non-preemptive tasks between some machines but also process preemptivetasks on other machines. These mobile robots are allowed to interrupt their preemptivetasks to carry out transportation of non-preemptive tasks when needed. The objective ofthe second problem is to minimize the time required to complete all tasks while takingaccount of precedence constraints.To deal with each mentioned scheduling problem, each mathematical model isfirst formulated. This allows describing each problem and finding optimal solutions foreach one. However, the formulated mathematical models could only be applicable tosmall-scale problems in practice due to the significant increase of computation time asthe problem size grows. Note that making schedules of mobile robots is part of real-timeoperations of production managers. Hence to deal with large-scale applications, eachheuristic based on genetic algorithms is then developed to find near-optimal solutionswithin a reasonable computation time for each problem. The quality of these solutions isthen compared and evaluated by using the solutions of the mathematical models asreference points. The results from numerical experiments in this thesis show that theproposed heuristics are capable of solving problems of various sizes and more efficientthan the mathematical models in terms of the objective values when giving the samelimited computation time. The research results are useful for production managers tomake decisions at operational levels and the proposed heuristics could be also applied toa variety of tasks of not only mobile robots but also automatic guided vehicles.

AB - This thesis addresses the issues of scheduling of mobile robot(s) at operational levels ofmanufacturing systems. More specifically, two problems of scheduling of a singlemobile robot with part-feeding tasks and scheduling of multiple mobile robots withpreemptive tasks are taken into account. For the first scheduling problem, a singlemobile robot is considered to collect and transport container of parts and empty theminto machine feeders where needed. A limit on carrying capacity of the single mobilerobot and hard time windows of part-feeding tasks are considered. The objective of thefirst problem is to minimize the total traveling time of the single mobile robot andthereby increase its availability. For the second scheduling problem, a fleet of mobilerobots 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 theothers are preemptive. The considered mobile robots have capabilities to not onlytransport non-preemptive tasks between some machines but also process preemptivetasks on other machines. These mobile robots are allowed to interrupt their preemptivetasks to carry out transportation of non-preemptive tasks when needed. The objective ofthe second problem is to minimize the time required to complete all tasks while takingaccount of precedence constraints.To deal with each mentioned scheduling problem, each mathematical model isfirst formulated. This allows describing each problem and finding optimal solutions foreach one. However, the formulated mathematical models could only be applicable tosmall-scale problems in practice due to the significant increase of computation time asthe problem size grows. Note that making schedules of mobile robots is part of real-timeoperations of production managers. Hence to deal with large-scale applications, eachheuristic based on genetic algorithms is then developed to find near-optimal solutionswithin a reasonable computation time for each problem. The quality of these solutions isthen compared and evaluated by using the solutions of the mathematical models asreference points. The results from numerical experiments in this thesis show that theproposed heuristics are capable of solving problems of various sizes and more efficientthan the mathematical models in terms of the objective values when giving the samelimited computation time. The research results are useful for production managers tomake decisions at operational levels and the proposed heuristics could be also applied toa variety of tasks of not only mobile robots but also automatic guided vehicles.

M3 - Ph.D. thesis

SN - 87-91200-64-4

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

PB - Institut for Mekanik og Produktion, Aalborg Universitet

ER -

Dang VQ. DEVELOPMENT OF GENETIC ALGORITHM-BASED METHODOLOGY FOR SCHEDULING OF MOBILE ROBOTS. Institut for Mekanik og Produktion, Aalborg Universitet, 2014. 208 s.