1,722,394 research outputs found
Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems
Full text linkWe study pseudo-polynomial formulations for the classical bin packing and cutting stock problems. We first propose an overview of dominance and equivalence relations among the main pattern-based and pseudo-polynomial formulations from the literature. We then introduce reflect, a new formulation that uses just half of the bin capacity to model an instance and needs significantly fewer constraints and variables than the classical models.We propose upper- A nd lower-bounding techniques that make use of column generation and dual information to compensate reflect weaknesses when bin capacity is too high. We also present nontrivial adaptations of our techniques that solve two interesting problem variants, namely the variable-sized bin packing problem and the bin packing problem with item fragmentation. Extensive computational tests on benchmark instances show that our algorithms achieve state of the art results on all problems, improving on previous algorithms and finding several new proven optimal solutions. A
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Rich vehicle routing with auxiliary depots and anticipated deliveries: An application to pharmaceutical distribution
Full text linkWe present and solve a rich vehicle routing problem based on a practical distribution problem faced by a third-party logistics provider, whose aim is to deliver pharmaceutical products to healthcare facilities in Tuscany. The problem is characterized by having multiple depots, a heterogeneous fleet of vehicles, flexible time windows, periodic demands, incompatibilities between vehicles and customers, a maximum duration for the routes, and a maximum number of customers per route. A multi-start iterated local search algorithm making use of several neighborhoods is proposed to solve the problem. The algorithm has been tested on a large number of instances and obtained good results, both on the real case study and on a number of artificially generated instances
A branch-and-price algorithm for the temporal bin packing problem
Full text linkWe study an extension of the classical Bin Packing Problem, where each item consumes the bin capacity during a given time window that depends on the item itself. The problem asks for finding the minimum number of bins to pack all the items while respecting the bin capacity at any time instant. A polynomial-size formulation, an exponential-size formulation, and a number of lower and upper bounds are studied. A branch-and-price algorithm for solving the exponential-size formulation is introduced. An overall algorithm combining the different methods is then proposed and tested through extensive computational experiments
Scheduling of Parallel Print Machines with Sequence-Dependent Setup Costs: A Real-World Case Study
No full textIn the present work, we consider a real-world scheduling problem arising in the color printing industry. The problem consists in assigning print jobs to a heterogeneous set of flexographic printer machines, as well as in finding a processing sequence for the sets of jobs assigned to each printer. The aim is to minimize a weighted sum of total weighted tardiness and total setup times. The machines are characterized by a limited sequence of color groups and can equip additional components (e.g., embossing rollers and perforating rolls) to process jobs that require specific treatments. The process to equip a machine with an additional component or to clean a color group takes a long time, with the effect of significantly raising the setup costs. Furthermore, the time required to clean a color group between two different jobs depends directly on the involved colors. To tackle the problem, we propose a constructive heuristic followed by some local search procedures that are used one after the other in an iterative way. Extensive tests on real-world instances prove that the proposed algorithm can obtain very good-quality solutions within a limited computing time
Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization
Full text linkThis paper addresses the parallel machine scheduling problem with family dependent setup times and total weighted completion time minimization. In this problem, when two jobs j and k are scheduled consecutively on the same machine, a setup time is performed between the finishing time of j and the starting time of k if and only if j and k belong to different families. The problem is strongly NP-hard and is commonly addressed in the literature by heuristic approaches and by branch-and-bound algorithms. Achieving proven optimal solution is a challenging task even for small size instances. Our contribution is to introduce five novel mixed integer linear programs based on concepts derived from one-commodity, arc-flow and set covering formulations. Numerical experiments on more than 13000 benchmark instances show that one of the arc-flow models and the set covering model are quite efficient, as they provide on average better solutions than state-of-the-art approaches, with shorter computation times, and solve to proven optimality a large number of open instances from the literature
Eventi e News nei Mercati Finanziari
No full textIl mercato finanziario domestico ed internazionale si è sempre più allontanato,
nell’ultimo ventennio, dalle ipotesi di efficienza perfetta ed assenza di attriti
nella formazione dei prezzi, postulati dalla teoria ed in qualche caso osservabili
– almeno temporaneamente – in alcuni segmenti dei mercati finanziari. In questo
clima si sono sempre maggiormente affermati gli schemi interpretativi della
finanza comportamentale, di cui costituiscono un importante strumento empirico
gli Event Studies (ES), estesamente descritti in questo libro
A GRASP for a real-world scheduling problem with unrelated parallel print machines and sequence-dependent setup times
No full textWe consider a real-world scheduling problem arising in the colour printing industry. The problem consists in assigning print jobs to a heterogeneous set of flexographic printer machines and finding a processing sequence for the jobs assigned to each machine. The machines are characterised by a limited sequence of colour groups and can equip additional components (e.g. embossing rollers and perforating rolls) to process jobs that require specific treatments. The process to equip a machine with an additional component or to clean a colour group takes a long time, with the effect of significantly raising the setup times. The aim is to minimise a weighted sum of total weighted tardiness and total setup time. The problem derives from the activities of an Italian food packaging company. To solve it, we developed a greedy randomised adaptive search procedure equipped with several local search procedures. The excellent performance of the algorithm is proved by extensive computational experiments on real-world instances, for which it produced good-quality solutions within a limited computing time. The algorithm is currently in use at the company to support their weekly scheduling decisions
- …
