Despite the continuous evolution in computers and information technology, real-world
combinatorial optimization problems are NP-problems, in particular in the domain of
planning and scheduling. Thus, although exact techniques from the Operations Research
(OR) field, such as Linear Programming, could be applied to solve optimization problems,
they are difficult to apply in real-world scenarios since they usually require too much computational
time, i.e: an optimized solution is required at an affordable computational time.
Furthermore, decision makers often face different and typically opposing goals, then resulting
multi-objective optimization problems. Therefore, approximate techniques from
the Artificial Intelligence (AI) field are commonly used to solve the real world problems.
The AI techniques provide richer and more flexible representations of real-world (Gomes
2000), and they are widely used to solve these type of problems. AI heuristic techniques
do not guarantee the optimal solution, but they provide near-optimal solutions in a reasonable
time. These techniques are divided into two broad classes of algorithms: constructive
and local search methods (Aarts and Lenstra 2003). They can guide their search processes
by means of heuristics or metaheuristics depending on how they escape from local optima
(Blum and Roli 2003). Regarding multi-objective optimization problems, the use of AI
techniques becomes paramount due to their complexity (Coello Coello 2006).
Nowadays, the point of view for planning and scheduling tasks has changed. Due to
the fact that real world is uncertain, imprecise and non-deterministic, there might be unknown
information, breakdowns, incidences or changes, which become the initial plans
or schedules invalid. Thus, there is a new trend to cope these aspects in the optimization
techniques, and to seek robust solutions (schedules) (Lambrechts, Demeulemeester, and
Herroelen 2008).
In this way, these optimization problems become harder since a new objective function
(robustness measure) must be taken into account during the solution search. Therefore,
the robustness concept is being studied and a general robustness measure has been developed
for any scheduling problem (such as Job Shop Problem, Open Shop Problem,
Railway Scheduling or Vehicle Routing Problem). To this end, in this thesis, some techniques
have been developed to improve the search of optimized and robust solutions in
planning and scheduling problems. These techniques offer assistance to decision makers
to help in planning and scheduling tasks, determine the consequences of changes, provide
support in the resolution of incidents, provide alternative plans, etc.
As a case study to evaluate the behaviour of the techniques developed, this thesis focuses
on problems related to container terminals. Container terminals generally serve
as a transshipment zone between ships and land vehicles (trains or trucks). In (Henesey
2006a), it is shown how this transshipment market has grown rapidly. Container terminals
are open systems with three distinguishable areas: the berth area, the storage yard,
and the terminal receipt and delivery gate area. Each one presents different planning and
scheduling problems to be optimized (Stahlbock and Voß 2008). For example, berth allocation,
quay crane assignment, stowage planning, and quay crane scheduling must be
managed in the berthing area; the container stacking problem, yard crane scheduling, and
horizontal transport operations must be carried out in the yard area; and the hinterland
operations must be solved in the landside area.
Furthermore, dynamism is also present in container terminals. The tasks of the container
terminals take place in an environment susceptible of breakdowns or incidences. For
instance, a Quay Crane engine stopped working and needs to be revised, delaying this
task one or two hours. Thereby, the robustness concept can be included in the scheduling
techniques to take into consideration some incidences and return a set of robust schedules.
In this thesis, we have developed a new domain-dependent planner to obtain more effi-
cient solutions in the generic problem of reshuffles of containers. Planning heuristics and
optimization criteria developed have been evaluated on realistic problems and they are
applicable to the general problem of reshuffling in blocks world scenarios.
Additionally, we have developed a scheduling model, using constructive metaheuristic
techniques on a complex problem that combines sequences of scenarios with different
types of resources (Berth Allocation, Quay Crane Assignment, and Container Stacking
problems). These problems are usually solved separately and their integration allows
more optimized solutions.
Moreover, in order to address the impact and changes that arise in dynamic real-world
environments, a robustness model has been developed for scheduling tasks. This model
has been applied to metaheuristic schemes, which are based on genetic algorithms. The
extension of such schemes, incorporating the robustness model developed, allows us to
evaluate and obtain more robust solutions. This approach, combined with the classical
optimality criterion in scheduling problems, allows us to obtain, in an efficient in way,
optimized solution able to withstand a greater degree of incidents that occur in dynamic
scenarios. Thus, a proactive approach is applied to the problem that arises with the presence
of incidences and changes that occur in typical scheduling problems of a dynamic real world. / Rodríguez Molins, M. (2015). Optimization and Robustness in Planning and Scheduling Problems. Application to Container Terminals [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/48545 / TESIS
| Identifer | oai:union.ndltd.org:upv.es/oai:riunet.upv.es:10251/48545 |
| Date | 31 March 2015 |
| Creators | Rodríguez Molins, Mario |
| Contributors | Barber Sanchís, Federico, Salido Gregorio, Miguel Angel, Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació |
| Publisher | Universitat Politècnica de València |
| Source Sets | Universitat Politècnica de València |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/acceptedVersion |
| Rights | http://rightsstatements.org/vocab/InC/1.0/, info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds