ILS-ESP An efficient, simple, and parameter-free algorithm for solving the permutation flow-shop problem

From a managerial point of view, the more effcient, simple, and parameter-free (ESP) an algorithm is, the more likely it will be used in practice for solving real-life problems. Following this principle, an ESP algorithm for solving the Permutation Flowshop Sequencing Problem (PFSP) is proposed in this article. Using an Iterated Local Search (ILS) framework, the so-called ILS-ESP algorithm is able to compete in performance with other well-known ILS-based approaches, which are considered among the most effcient algorithms for the PFSP. However, while other similar approaches still employ several parameters that can affect their performance if not properly chosen, our algorithm does not require any particular fine-tuning process since it uses basic "common sense" rules for the local search, perturbation, and acceptance criterion stages of the ILS metaheuristic. Our approach defines a new operator for the ILS perturbation process, a new acceptance criterion based on extremely simple and transparent rules, and a biased randomization process of the initial solution to randomly generate different alternative initial solutions of similar quality -which is attained by applying a biased randomization to a classical PFSP heuristic. This diversification of the initial solution aims at avoiding poorly designed starting points and, thus, allows the methodology to take advantage of current trends in parallel and distributed computing. A set of extensive tests, based on literature benchmarks, has been carried out in order to validate our algorithm and compare it against other approaches. These tests show that our parameter-free algorithm is able to compete with state-of-the-art metaheuristics for the PFSP. Also, the experiments show that, when using parallel computing, it is possible to improve the top ILS-based metaheuristic by just incorporating to it our biased randomization process with a high-quality pseudo-random number generator.

Optimised search heuristic combining valid inequalities and tabu search

This paper presents an Optimised Search Heuristic that combines a tabu search method with the verification of violated valid inequalities. The solution delivered by the tabu search is partially destroyed by a randomised greedy procedure, and then the valid inequalities are used to guide the reconstruction of a complete solution. An application of the new method to the Job-Shop Scheduling problem is presented.

Restless bandits, partial conservation laws and indexability

We show that if performance measures in a stochastic scheduling problem satisfy a set of so-called partial conservation laws (PCL), which extend previously studied generalized conservation laws (GCL), then the problem is solved optimally by a priority-index policy for an appropriate range of linear performance objectives, where the optimal indices are computed by a one-pass adaptive-greedy algorithm, based on Klimov's. We further apply this framework to investigate the indexability property of restless bandits introduced by Whittle, obtaining the following results: (1) we identify a class of restless bandits (PCL-indexable) which are indexable; membership in this class is tested through a single run of the adaptive-greedy algorithm, which also computes the Whittle indices when the test is positive; this provides a tractable sufficient condition for indexability; (2) we further indentify the class of GCL-indexable bandits, which includes classical bandits, having the property that they are indexable under any linear reward objective. The analysis is based on the so-called achievable region method, as the results follow fromnew linear programming formulations for the problems investigated.

Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part I, the single-station case

We address the performance optimization problem in a single-stationmulticlass queueing network with changeover times by means of theachievable region approach. This approach seeks to obtainperformance bounds and scheduling policies from the solution of amathematical program over a relaxation of the system's performanceregion. Relaxed formulations (including linear, convex, nonconvexand positive semidefinite constraints) of this region are developedby formulating equilibrium relations satisfied by the system, withthe help of Palm calculus. Our contributions include: (1) newconstraints formulating equilibrium relations on server dynamics;(2) a flow conservation interpretation of the constraintspreviously derived by the potential function method; (3) newpositive semidefinite constraints; (4) new work decomposition lawsfor single-station multiclass queueing networks, which yield newconvex constraints; (5) a unified buffer occupancy method ofperformance analysis obtained from the constraints; (6) heuristicscheduling policies from the solution of the relaxations.

Restless bandits, linear programming relaxations and a primal-dual index heuristic

We develop a mathematical programming approach for the classicalPSPACE - hard restless bandit problem in stochastic optimization.We introduce a hierarchy of n (where n is the number of bandits)increasingly stronger linear programming relaxations, the lastof which is exact and corresponds to the (exponential size)formulation of the problem as a Markov decision chain, while theother relaxations provide bounds and are efficiently computed. Wealso propose a priority-index heuristic scheduling policy fromthe solution to the first-order relaxation, where the indices aredefined in terms of optimal dual variables. In this way wepropose a policy and a suboptimality guarantee. We report resultsof computational experiments that suggest that the proposedheuristic policy is nearly optimal. Moreover, the second-orderrelaxation is found to provide strong bounds on the optimalvalue.

Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case

We address the problem of scheduling a multi-station multiclassqueueing network (MQNET) with server changeover times to minimizesteady-state mean job holding costs. We present new lower boundson the best achievable cost that emerge as the values ofmathematical programming problems (linear, semidefinite, andconvex) over relaxed formulations of the system's achievableperformance region. The constraints on achievable performancedefining these formulations are obtained by formulatingsystem's equilibrium relations. Our contributions include: (1) aflow conservation interpretation and closed formulae for theconstraints previously derived by the potential function method;(2) new work decomposition laws for MQNETs; (3) new constraints(linear, convex, and semidefinite) on the performance region offirst and second moments of queue lengths for MQNETs; (4) a fastbound for a MQNET with N customer classes computed in N steps; (5)two heuristic scheduling policies: a priority-index policy, anda policy extracted from the solution of a linear programmingrelaxation.

Exploiting fitness distance correlation of set covering problems

The set covering problem is an NP-hard combinatorial optimization problemthat arises in applications ranging from crew scheduling in airlines todriver scheduling in public mass transport. In this paper we analyze searchspace characteristics of a widely used set of benchmark instances throughan analysis of the fitness-distance correlation. This analysis shows thatthere exist several classes of set covering instances that have a largelydifferent behavior. For instances with high fitness distance correlation,we propose new ways of generating core problems and analyze the performanceof algorithms exploiting these core problems.

Tenda Virtual orientada a compres per escaneig amb el telèfon mòbil

CMS (Sistema Gestor de Continguts) és una tecnologia en ple auge que permet implantar solucions web d'una manera senzilla, econòmica i amb un fàcil manteniment per part dels usuaris que en fan ús. Aquest projecte és un estudi que pretén analitzar i escollir el millor CMS dirigit a comerç electrònic d'entre el ventall existent actualment al mercat, creant un document que serveixi de referent o guia a qualsevol persona interessada en implantar un sistema d'aquestes característiques. A més, es centrarà a la programació d'un component instal·lable pel CMS escollit que permeti introduir-nos a la creació d'extensions i ens formi en l'àmbit de la programació web. Aquest component el podrem afegir al CMS i permetrà realitzar compres escanejant codis amb el telèfon mòbil.

Note on the blocking flow shop problem

We present some results attained with different algorithms for the Fm|block|Cmax problem using as experimental data the well-known Taillard instances.

Plataforma de resolució de problemes RCPSP utilitzant SMT

El problema d'operacions (scheduling) és un procés de presa de decisions quejuga un paper molt important en organitzacions de manufactura i serveis, jaque té una aplicació a la producció, transport i distribució, i a la comunicaciói processament d'informació, entre d'altres. Consisteix en assignar d'unamanera apropiada els recursos disponibles per al processament de tasquesde manera que es puguin optimitzar els objectius de l’organització.Com cas particular de la programació d'operacions, hi ha la programacióde projectes (Project Scheduling), que és el procés de planificar, organitzari controlar activitats i recursos per aconseguir un objectiu concret, generalmentamb limitacions de temps, recursos o costos. Dins aquest grup essituen els problemes de programació de projectes (PSP), que és un nomgenèric que es dóna a tota una classe de problemes en els quals és necessàriala programació de manera òptima el temps, el cost i els recursos dels projectes.La finalitat d'aquest projecte és crear una plataforma RCPSP que puguillegir diferents formats d'entrada (fitxers del tipus :.rcp,.sch,.sm,.data,.pat),pre-processar-los, codificar-los a través de diferents modelitzacions (TaskRD,TimeRD...) per tal de poder-los passar a instàncies SMT i poder executar-losa través de la API de Yices. L'objectiu és trobar el temps d'inici percada activitat de manera que es minimitzi la longitud del makespan senseque es violin les restriccions.Cal dissenyar una aplicació en C++, que sigui escalable i que puguiaconseguir el resultat del problema en el temps més òptim possible

Procedimientos de exploración de entornos para la programación de operaciones en una máquina con tiempos de preparación

objetivo de minimizar el retraso total en un ambiente con preparaciones quedependen de la secuencia. Se comparan los resultados obtenidos mediante laaplicación de los procedimientos de exploración de entornos AED, ANED,Recocido Simulado, Algoritmos Genéticos, Búsqueda Tabú y GRASP alproblema planteado. Los resultados sugieren que la Búsqueda Tabú es unatécnica viable de solución que puede proporcionar buenas soluciones cuandose considera el objetivo retraso total con tiempos de preparación dependientesde la secuencia.

What to consider for applying backfilling on non-dedicated environments

The resource utilization level in open laboratories of several universities has been shown to be very low. Our aim is to take advantage of those idle resources for parallel computation without disturbing the local load. In order to provide a system that lets us execute parallel applications in such a non-dedicated cluster, we use an integral scheduling system that considers both Space and Time sharing concerns. For dealing with the Time Sharing (TS) aspect, we use a technique based on the communication-driven coscheduling principle. This kind of TS system has some implications on the Space Sharing (SS) system, that force us to modify the way job scheduling is traditionally done. In this paper, we analyze the relation between the TS and the SS systems in a non-dedicated cluster. As a consequence of this analysis, we propose a new technique, termed 3DBackfilling. This proposal implements the well known SS technique of backfilling, but applied to an environment with a MultiProgramming Level (MPL) of the parallel applications that is greater than one. Besides, 3DBackfilling considers the requirements of the local workload running on each node. Our proposal was evaluated in a PVM/MPI Linux cluster, and it was compared with several more traditional SS policies applied to non-dedicated environments.

Cartografia detallada de sòls en àrees de regadiu de Catalunya

La superfície regada a Catalunya és d'unes 260.00 ha. aproximadament, la qual constitueix el 26 % de l'àrea conreada i el 8 % de l'àrea total; tot i així, en l'àrea regada es produeix, aproximadament, el 68 % del producte final agrari. El pes econòmic de l'àrea regada, la facilitat més gran per introduir noves tecnologies amb una rendibilitat superior i la necessitat que tenen les mateixes tecnologies de disposar d'una informació de base van fer aconsellable iniciar les tasques de cartografia de sòls del Departament d'Agricultura, Ramaderia i Pesca (DARP) en les àrees indicades. La naturalesa del problema plantejat, consistent bàsicament en l'aplicació de tecnologia agrícola (programació de regs, utilització de l'aigua de reg sota condicions de salinitat-sodicitat, plans de fertilització, reg de sòls guixencs, i selecció de sòls segons l'aptitud per als cultius, etc.), i també la grandària de les explotacions i parcel·les, obliguen a disposar d'una acurada informació quantitativa i a plantejar una cartografia de sòls detallada. En aquest treball s'exposen els estudis realitzats fins ara sobre cartografia de sòls i les aplicacions que s'han efectuat o que es preveu que s'efectuaran en un termini curt. Es comenta la problemàtica sorgida en el transcurs de la realització d'aquests treballs cartogràfics, es revisen les aplicacions dutes a terme i les dificultats que s'han trobat en la transmissió i la transferència de la informació generada al sector agrari en general i als tècnics de l'Administració.

¿Turnos o demanda? En el proyecto de redes de distribución de riego a presión

Actualmente vuelve a ser viable la organización mediante turnos de redes de distribución de riego a presión gracias al desarrollo de sistemas de automáticos de telegestión. La organización por turnos supone una disminución de los caudales en la red y el consiguiente ahorro económico. En la comunicación se presentan diversas expresiones sencillas para calcular la disminución relativa de caudales conseguida mediante la organización por turnos respecto a la demanda. Dicha disminución depende del número de hidrantes abastecidos por un tramo y de la probabilidad de que los hidrantes estén abiertos. Se ha contrastado los resultados de las expresiones propuestas con datos de proyecto y se consiguen buenos ajustes. El ahorro económico obtenido con la organización por turnos respecto a la demanda se puede estimar entre un 26 y un 49 % el ahorro medio de caudales.

Irrigation performance and gross water productivity in furrow-irrigated ornamental tree production

In the ornamental plant production region of Girona (Spain), which is one of the largest of its kind in southern Europe, most of the surface is irrigated using wide blocked-end furrows. The objectives of this paper were: (1) to evaluate the irrigation scheduling methods used by ornamental plant producers; (2) to analyse different scenarios in order to assess how they affect irrigation performance; (3) to evaluate the risk of deep percolation; and (4) to calculate gross water productivity. A two-year study in a representative commercial field, planted with Prunus cerasifera ‘Nigra’, was carried out. The irrigation dose applied by the farmers was slightly smaller than the required water dose estimated by the use of two different methods: the first based on soil water content, and the second based on evapotranspiration. Distribution uniformity and application eff iciency were high, with mean values above 87%. Soil water content measurements revealed that even at the end of the furrow, where the infiltrated water depth was greatest, more than 90% of the infiltrated water was retained in the shallowest 40 cm of the soil; accordingly, the risk of water loss due to deep percolation was minimal. Gross water productivity for ornamental tree production was € 11.70 m–3, approximately 20 times higher than that obtained with maize in the same region.