CRIS - TEI of Epirushttp://cris.teiep.gr/jspuiThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Tue, 18 Dec 2018 19:09:47 GMT2018-12-18T19:09:47Z50141A multi-staged algorithmic process for the solution of the examination timetabling problemhttp://cris.teiep.gr/jspui/handle/123456789/1295Title: A multi-staged algorithmic process for the solution of the examination timetabling problem
Authors: Γκόγκος, Χρήστος; Αλεφραγκής, Παναγιώτης; Χούσος, Ευθύμιος
Abstract: We present an approach for the examination timetabling problem as defined in the
second International Timetabling Competition (http://www.cs.qub.ac.uk/itc2007). The solution
approach can be considered as an implementation of the GRASP (Greedy Randomized Adaptive
Search Procedure) method with the combination of several other metaheuristics. Three stages are
employed. The first stage is responsible for the construction of a relatively high quality feasible
solution while the second stage improves it using simulated annealing local search. The final stage
uses mathematical programming and analyzes each examination period in isolation proposing
movements of exams to other rooms resulting in further improvement of the solution quality. The
procedure produces feasible solutions for each dataset provided under the runtime limit imposed
by the competition’s rules. Results are presented and analyzed.
Description: http://www.patatconference.org/patat2008/proceedings/Gogos-HC2b.pdf
Fri, 01 Aug 2008 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/12952008-08-01T00:00:00ZAn improved multi-staged algorithmic process for the solution of the examination timetabling problemhttp://cris.teiep.gr/jspui/handle/123456789/1293Title: An improved multi-staged algorithmic process for the solution of the examination timetabling problem
Authors: Γκόγκος, Χρήστος; Αλεφραγκής, Παναγιώτης; Χούσος, Ευθύμιος
Abstract: The efficient creation of examination timetables is a recurring and important problem for universities worldwide. Good timetables typically are characterized by balanced distances between consecutive exams for all students. In this contribution an approach for the examination timetabling problem as defined in the second International Timetabling Competition (http://www.cs.qub.ac.uk/itc2007/) is presented. The solution approach is managed on the top level by GRASP (Greedy Randomized Adaptive Search Procedure) and it involves several optimization algorithms, heuristics and metaheuristics. A construction phase is executed first producing a relatively high quality feasible solution and an improvement phase follows that further ameliorates the produced timetable. Each phase consists of stages that are consumed in a circular fashion. The procedure produces feasible solutions for each dataset provided under the runtime limit imposed by the rules of the ITC07 competition. Results are presented and analyzed.
Sun, 01 Apr 2012 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/12932012-04-01T00:00:00ZGraphics Processing Unit acceleration of a memetic algorithm for the Examination Timetabling Problemhttp://cris.teiep.gr/jspui/handle/123456789/1308Title: Graphics Processing Unit acceleration of a memetic algorithm for the Examination Timetabling Problem
Authors: Κολώνιας, Βασίλειος; Γούλας, Γεώργιος; Αλεφραγκής, Παναγιώτης; Γκόγκος, Χρήστος; Χούσος, Ευθύμιος
Fri, 01 Aug 2014 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/13082014-08-01T00:00:00ZA systematic two phase approach for the nurse rostering problemhttp://cris.teiep.gr/jspui/handle/123456789/1294Title: A systematic two phase approach for the nurse rostering problem
Authors: Βαλουξής, Χρήστος; Γκόγκος, Χρήστος; Γούλας, Γεώργιος; Αλεφραγκής, Παναγιώτης; Χούσος, Ευθύμιος
Abstract: Nurse rostering is an NP-hard combinatorial problem which makes it extremely difficult to efficiently solve real life problems due to their size and complexity. Usually real problem instances have complicated work rules related to safety and quality of service issues in addition to rules about quality of life of the personnel. For the aforementioned reasons computer supported scheduling and rescheduling for the particular problem is indispensable. The specifications of the problem addressed were defined by the First International Nurse Rostering Competition (INRC2010) sponsored by the leading conference in the Automated Timetabling domain, PATAT-2010. Since the competition imposed quality and time constraint requirements, the problem instances were partitioned into sub-problems of manageable computational size and were then solved sequentially using Integer Mathematical Programming. A two phase strategy was implemented where in the first phase the workload for each nurse and for each day of the week was decided while in the second phase the specific daily shifts were assigned. In addition, local optimization techniques for searching across combinations of nurses’ partial schedules were also applied. This sequence is repeated several times depending on the available computational time. The results of our approach and the submitted software produced excellent solutions for both the known and the hidden problem instances, which in respect gave our team the first position in all tracks of the INRC-2010 competition.
Fri, 01 Jun 2012 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/12942012-06-01T00:00:00ZSolving the examination timetabling problem in GPUshttp://cris.teiep.gr/jspui/handle/123456789/1307Title: Solving the examination timetabling problem in GPUs
Authors: Κολώνιας, Βασίλειος; Γούλας, Γεώργιος; Γκόγκος, Χρήστος; Αλεφραγκής, Παναγιώτης; Χούσος, Ευθύμιος
Abstract: The examination timetabling problem belongs to the class of combinatorial
optimization problems and is of great importance for every University. In this paper, a
hybrid evolutionary algorithm running on a GPU is employed to solve the examination
timetabling problem. The hybrid evolutionary algorithm proposed has a genetic algorithm
component and a greedy steepest descent component. The GPU computational capabilities
allow the use of very large population sizes, leading to a more thorough exploration of the
problem solution space. The GPU implementation, depending on the size of the problem, is
up to twenty six times faster than the identical single-threaded CPU implementation of the
algorithm. The algorithm is evaluated with the well known Toronto datasets and compares
well with the best results found in the bibliography. Moreover, the selection of the encoding
of the chromosomes and the tournament selection size as the population grows are examined
and optimized. The compressed sparse row format is used for the conflict matrix and was
proven essential to the process, since most of the datasets have a small conflict density, which
translates into an extremely sparse matrix.
Tue, 01 Jul 2014 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/13072014-07-01T00:00:00ZPursuit of better results for the examination timetabling problem using grid resourceshttp://cris.teiep.gr/jspui/handle/123456789/1297Title: Pursuit of better results for the examination timetabling problem using grid resources
Authors: Γκόγκος, Χρήστος; Γούλας, Γεώργιος; Αλεφραγκής, Παναγιώτης; Χούσος, Ευθύμιος
Abstract: Examination timetabling for universities is a difficult optimization problem with its main objective being to produce the best possible schedule for every student participating. Metaheuristics are a common way of coping with this problem mainly due to their flexibility in adapting to complex real world situations. In this contribution, Grid resources are exploited in order to locate solutions that might have been unreachable in a reasonable time using the processing power of a single computer.
Description: DOI: 10.1109/SCIS.2009.4927014
Thu, 01 Jan 2009 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/12972009-01-01T00:00:00ZDAG Scheduling using Integer Programming in heterogeneous parallel execution environmentshttp://cris.teiep.gr/jspui/handle/123456789/1299Title: DAG Scheduling using Integer Programming in heterogeneous parallel execution environments
Authors: Βαλουξής, Χρήστος; Γκόγκος, Χρήστος; Αλεφραγκής, Παναγιώτης; Γούλας, Γεώργιος; Βώρος, Νικόλαος; Χούσος, Ευθύμιος
Abstract: A computer program can be represented by a Directed Acyclic Graph (DAG) in
order to capture the dependencies between the individual tasks that should be executed each
time the program runs. This paper proposes a mathematical model of Integer Programming that
can be applied in order to schedule the tasks in the presence of multiple processors serving as
the execution environment. The target is to minimize the overall execution time of the DAG
known as schedule length or makespan. An approach called MATH using the full model is
applied to small sized problems and then a more elaborate approach called MATHL is
presented where the DAG is partitioned to levels. Levels are formed according to the hops
needed for each node to be reached starting from the source node. Hence sub-problems have
manageable size and can be solved in a timely manner. Consecutive optimal solutions for each
level result in a high quality schedule for the overall problem even for cases consisting of
several hundreds of nodes. Results show that this method constantly gives very good results
and it is compared favorably with other approaches to the problem that can be found in the
bibliography.
Description: http://www.alma-project.eu/downloads/Mista2013.pdf
Tue, 01 Jan 2013 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/12992013-01-01T00:00:00ZApplication of heuristics, genetic algorithms & integer programming at a public enterprise water pump scheduling systemhttp://cris.teiep.gr/jspui/handle/123456789/1305Title: Application of heuristics, genetic algorithms & integer programming at a public enterprise water pump scheduling system
Authors: Γκόγκος, Χρήστος; Αλεφραγκής, Παναγιώτης; Χούσος, Ευθύμιος
Abstract: In this paper the problem of minimizing the electricity cost required by a water storage and
disposal system is analyzed. Three solution approaches are presented focused in the way that
various pumps will be scheduled to operate and satisfy prospected water demand while at the
same time respect availability of water and reservoirs capacity. The first solution uses a
heuristic approach closely related to the way a human operator might have used to solve the
problem. The second solution uses mathematical programming, formulates the problem as an
Integer Programming problem and solve it by using a Branch and Bound commercial solver.
Finally the third solution uses Genetic Algorithms and defines a fitness function describing the
attractiveness of each solution for a set of solutions and through a number of evolution steps
creates a population with desirable characteristics. A comparative study of the three
approaches is presented. The actual formulas that compute the electricity cost is used for the
comparisons. Those formulas state the fact that demand peaks especially during high demand
periods result in high electricity cost. Data used in our experiments were provided by the
municipal enterprise of water supplies and sewage of Chania (Crete).
Description: http://pci2007.upatras.gr/proceedings/PCI2007_volA/A_579-589_Gogos.pdf
Tue, 01 May 2007 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/13052007-05-01T00:00:00ZAssigning and scheduling hierarchical task graphs to heterogeneous resourceshttp://cris.teiep.gr/jspui/handle/123456789/1309Title: Assigning and scheduling hierarchical task graphs to heterogeneous resources
Authors: Αλεφραγκής, Παναγιώτης; Γκόγκος, Χρήστος; Βαλουξής, Χρήστος; Γούλας, Γεώργιος; Βώρος, Νικόλαος; Χούσος, Ευθύμιος
Abstract: Task Scheduling is an important problem having many practical applications. More often than not,
precedence constraints exist between tasks, and a common way to capture them is through
Directed Acyclic Graphs (DAGs). A DAG might contain a great number of tasks representing
complex real life scenarios. It might be the case that logical groupings of tasks exist giving a
hierarchical nature to the graph. Such Hierarchical Task Graphs (HTGs) have nodes that are
further analyzed to DAGs or to other HTGs. In this paper a method of solving an HTG problem is
presented based on the idea of gradually solving the problem by replacing subgraphs with virtual
nodes. Integer Programming is used to generate virtual nodes that replace a subgraph, results from
solving the subgraph problem using. So a series of subproblems are solved and starting from the
deeper levels of the HTG a solution to the full problem emerges.
Fri, 01 Aug 2014 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/13092014-08-01T00:00:00ZPublic enterprise water pump scheduling systemhttp://cris.teiep.gr/jspui/handle/123456789/1298Title: Public enterprise water pump scheduling system
Authors: Γκόγκος, Χρήστος; Αλεφραγκής, Παναγιώτης; Χούσος, Ευθύμιος
Abstract: In this paper a mathematical model and a solution for the pump scheduling problem based on genetic algorithms is presented. The main objective is the reduction of the electricity costs of the water department for the pumping effort. The constraints are such as to maintain strategic security and reliability limits for each water reservoir. The reduction of the peaks during a scheduling period is equivalent to the minimization of the electricity costs and this is in fact used in the solution process of our experiment. Actual results with the pump scheduling results of Chania, Greece are also presented
Description: DOI: 10.1109/ETFA.2005.1612761
Thu, 01 Sep 2005 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/12982005-09-01T00:00:00ZERMIS: A helicopter taxi company software support system based on GPS, GSM and Web Serviceshttp://cris.teiep.gr/jspui/handle/123456789/1302Title: ERMIS: A helicopter taxi company software support system based on GPS, GSM and Web Services
Authors: Γούλας, Γεώργιος; Μπαρκαγιάννης, Β.; Γιαννούλης, Σ.; Γκόγκος, Χρήστος; Αλεφραγκής, Παναγιώτης; Φούντας, Π.; Βαλουξής, Χρήστος; Κούμπιας, Σ.; Χούσος, Ευθύμιος
Abstract: This paper describes the ERMIS system, specially designed to support the fleet and personnel scheduling and management issues, as well as to support various business collaboration issues for a helicopter taxi company. The implemented system offers a Web-based interface for the flying and stationary personnel and a software application running on a PDA with GSM and GPS capabilities for the pilots. The information flow and the business processes of the ERMIS system are based on XML Web services which makes the system open and interoperable with other company-owned information systems.
Description: DOI: 10.1109/ETFA.2006.355447
Fri, 01 Sep 2006 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/13022006-09-01T00:00:00ZDecomposing the High School problemhttp://cris.teiep.gr/jspui/handle/123456789/1290Title: Decomposing the High School problem
Authors: Βαλουξής, Χρήστος; Γκόγκος, Χρήστος; Αλεφραγκής, Παναγιώτης; Χούσος, Ευθύμιος
Description: http://www.patatconference.org/patat2012/proceedings/2_14.pdf
Sun, 01 Jan 2012 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/12902012-01-01T00:00:00ZDistributed scatter search for the examination timetabling problemhttp://cris.teiep.gr/jspui/handle/123456789/1301Title: Distributed scatter search for the examination timetabling problem
Authors: Γκόγκος, Χρήστος; Γούλας, Γεώργιος; Αλεφραγκής, Παναγιώτης; Κολώνιας, Βασίλειος; Χούσος, Ευθύμιος
Abstract: Examination Timetabling for Universities is a problem with significant practical
importance. It belongs to the general class of educational timetabling problems and has been
exposed to numerous approaches for solving it. We propose a parallel/distributed solution which is
based on the metaheuristic method Scatter Search combined with Path Relinking in an attempt to
diversify the search procedure by producing promising new timetables. Our approach improves on
the best publicly available results for the datasets of ITC2007 (International Timetabling
Competition 2007-2008). The constraint of limited execution time that was imposed by ITC2007
was disregarded in an effort to pursue the best values our approach could reach. We consider this
specific examination timetabling problem as a “test bed” for timetabling problems in general and
we expect to provide insight for developing effective solution processes for other practical
scheduling problems.
Description: http://doc.utwente.nl/75057/1/PATAT10_Proceedings.pdf#page=225
Sun, 01 Aug 2010 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/13012010-08-01T00:00:00ZSensor enabled rule based alarm system for the agricultural industryhttp://cris.teiep.gr/jspui/handle/123456789/1304Title: Sensor enabled rule based alarm system for the agricultural industry
Authors: Γκόγκος, Χρήστος; Αλεφραγκής, Παναγιώτης; Χούσος, Ευθύμιος
Abstract: This paper describes a system that generates intelligent alarms using sensor data located at various geographical locations. Users are informed, using a rule enabled engine whenever certain conditions demanding attention occur, through an SMS messaging system. The user can easily define, through a graphical user interface, new rules or update existing ones. An agricultural case study of the system is presented.
Description: DOI: 10.1109/EFTA.2007.4416880
Sat, 01 Sep 2007 00:00:00 GMThttp://cris.teiep.gr/jspui/handle/123456789/13042007-09-01T00:00:00Z