Search

In this paper, we continue describing the project and the experimentation of "Ricerca Operativa Applicazioni Reali" (ROAR; in English, Real Applications of Operations Research), a three-year project for higher secondary schools, introduced. ROAR is composed of three teaching units, addressed to Grades 10, 11, and 12, respectively, having the main aim to improve students' interest, motivation, and skills related to Science, Technology, Engineering, and Mathematics disciplines by integrating mathematics and computer science through operations research. In a previous paper, we reported on the design and implementation of the first unit, started in Spring 2021 at the scientific high school IIS Antonietti in Iseo (Brescia, Italy), in a Grade-10 class. Here, we focus on the second unit, carried out in Winter/Spring 2022 with the same students, now in a Grade-11 class. In particular, we describe objectives, prerequisites, topics and methods, the organization of the lectures, digital technologies used, and a challenging final project. Moreover, we analyze the feedback from students and teachers involved in the experimentation.

We introduce "Ricerca Operativa Applicazioni Reali" (ROAR; in English, "Real Applications of Operations Research"), a three-year project for higher secondary schools. Its main aim is to improve students' interest, motivation, and skills related to Science, Technology, Engineering, and Mathematics disciplines by integrating mathematics and computer science through operations research. ROAR offers examples and problems closely connected with students' everyday life or with the industrial reality, balancing mathematical modeling and algorithmics. The project is composed of three teaching units, addressed to grades 10, 11, and 12. The implementation of the first teaching unit took place in Spring 2021 at the scientific high school IIS Antonietti in Iseo (Brescia, Italy). In particular, in this paper, we provide a full description of this first teaching unit in terms of objectives, prerequisites, topics and methods, organization of the lectures, and digital technologies used. Moreover, we analyze the feedback received from students and teachers involved in the experimentation, and we discuss advantages and disadvantages related to distance learning that we had to adopt because of the COVID-19 pandemic.

The simple vehicle routing problem (VRP) is a common topic of discussion in introductory operations research/management science courses. The VRP can be framed in a variety of ways, and it can be difficult to solve to optimality. For solution purposes, introductory textbooks demonstrate how Excel's Evolutionary Solver (ES) add-in produces a routing. The ES utilizes a genetic algorithm with a heuristic stopping rule to produce a routing that is not guaranteed to be optimal. Beyond pointing out that search controls, such as maximum execution time, may be extended and followed by restart(s) of ES, textbook treatments do not offer alternative ways to continue the search for a possibly better routing. In this paper, a suite of ways is presented in which students may investigate beyond what ES produces or any other optimality-uncertain VRP solution method. The suite includes perturbation methods and other ways that function within an Excel spreadsheet environment that is popular with students and textbook writers. Because there is no demonstrable feature that confirms optimality, the student problem Solver must settle for a 'best found' result as unsettling as it may be. The incertitude is addressed.

Thus, (3) treats the constraints HT ht and HT ht implicitly, and works solely with the auxiliary support variables I y i . [Extracted from the article]

By simulating the change process of the inventory of scientific papers according to a mathematical model of the publishing process, we find that publication delay would cause statistical error of the scientific paper output indicator, i.e. the quantity of published papers. Based on a simulation model and the average publication delay, we construct an optimization algorithm of the actual scientific paper output using a nonlinear least squares algorithm and validate its accuracy. To simplify the solution process, we propose an approximate algorithm of the actual scientific paper output indicator which would help science and technology managers practically deduce an approximation of the actual indicator. This has implications for strategy decision making and allocation of resources for science and technology research by policy makers. [ABSTRACT FROM AUTHOR]

The article presents a list of working papers related to management science. Some of the papers include "A Primal-Dual Surrogate Simplex Algorithm: Comparison with the Criss Cross Method," by R. S. Garfinkel and P. L. Yu, "Optimal Impulsive Trajectory Rendezvous Using Projection-Restoration," by W. A. Gruver, and "Asymptotic Normality of the Extremum of Certain Sample Functions," by P. K. Sen.

Abstract: The aim of this note is to show that the optimization algorithm proposed in may not lead to the optimal solution in some cases. In fact, the optimization problem remains open if we do not apply the branch-and-bound method to solve it or compute all the objective values of minimal solutions of the feasible domain. [Copyright &y& Elsevier]

The papers are grouped into three categories: AI methods for manufacturing systems, AI developments specifically in semiconductor manufacturing, and AI in additive manufacturing and maintenance. They combine a deep neural network model and Markov decision processes (MDP) to rapidly generate near optimal dynamic control policies for problems that are too large to be only solved by MDP, thus showing the potential of machine learning in controlling unreliable manufacturing systems. [Extracted from the article]

Objectives: A well-developed appointment system can help increase the utilization of medical facilities in an outpatient department. This paper outlines the development of an appointment system that can make an outpatient department work more efficiently and improve patient satisfaction level., Methods: A Markov decision process model is proposed to schedule sequential appointments with the consideration of patient preferences in order to maximize the patient satisfaction level. Adaptive dynamic programming algorithms are developed to avoid the curse of dimensionality. These algorithms can dynamically capture patient preferences, update the value of being a state, and thus improve the appointment decisions., Results: Experiments were conducted to investigate the performance of the algorithms. The convergence behaviors under different settings, including the number of iterations needed for convergence and the accuracy of results, were examined. Bias-adjusted Kalman filter step-sizes were found to lead to the best convergence behavior, which stabilized within 5000 iterations. As for the effects of exploration and exploitation, it resulted in the best convergence behavior when the probability of taking a myopically optimal action equaled 0.9. The performance of value function approximation algorithm was greatly affected by the combination of basis functions. Under different combinations, errors varied from 2.7% to 8.3%. More preferences resulted in faster convergence, but required longer computation time., Conclusions: System parameters are adaptively updated as bookings are confirmed. The proposed appointment scheduling system could certainly contribute to better patient satisfaction level during the booking periods., (Copyright © 2014 Elsevier B.V. All rights reserved.)

This paper proposes a transmission-scheduling algorithm for interference management in broadband wireless access networks. The algorithm aims to minimize the cochannel interference using basestation coordination while still maintaining the other quality of service (QoS) requirements such as packet delay, throughput and packet loss. The interference reduction is achieved by avoiding (or minimizing) concurrent transmission of potential dominant interferers. Dynamic slot allocation based on traffic information in other cells/sectors is employed. In order to implement the algorithm in a distributed manner, basestations (BSs) have to exchange traffic information. Both real-time and non-real-time services are considered in this work. Results show that significant reduction in the packet error rate can be achieved without increasing the packet delay at low to medium loading values and with a higher but acceptable packet delay at high loading values. Since ARQ schemes can also be used for packet error rate reduction, we compare the performance of the proposed scheme with that of ARQ. Results indicate that although ARQ is more effective in reducing packet error rate, the proposed algorithm incurs much less packet delay particularly at medium to high loading. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This article discusses how a hybrid algorithm based on a genetic algorithm (GA) and linear programming helps minimize distribution costs for the Scandinavian pulp producer Sodra Cell. The GA considers a planner's perspective by defining an individual schedule as the sequences of routes for all ships in a fixed fleet. Because the GA operates on a pool of potential solutions, constantly adjusting them to better fit the requirements, it can suggest multiple solutions. Furthermore, it can serve as a core algorithm in a support system where one can apply small changes to the set of constraints without a cold start. Applying the GA to Sodra Cell's real-world case and comparing it to mixed-integer-programming approach revealed competitive results. INSET: Related Work in Genetic Algorithms..

The construction sector is a crucial contributor to the national and global economy. Therefore, improving the efficiency and effectiveness of construction projects can have a significant impact on gross domestic product (GDP). However, managing construction projects can be challenging due to the uncertainties and complexities involved. The three primary interrelated constraints of construction projects, namely, time, scope, and cost, require effective management to ensure successful completion. To optimize the time and cost of construction projects, various optimization models and techniques have been proposed in the literature. This paper presents a systematic review of the time-cost optimization models in construction management and proposes some future work to improve the solution of the considered problem. The review categorizes the existing models into three categories: exact models, approximate models, and hybrid algorithm models. The exact models provide optimal solutions but require a lot of computational time and may not be efficient in solving multi-objective and large-scale problems. The approximate models provide near-optimal solutions and reduce computational effort but may not be efficient in solving large-scale projects. The hybrid algorithm models combine the good properties of different algorithms to provide high-quality and efficient solutions. The purpose of this paper is accomplished through a systematic literature review following the Preferred Reporting Items for Systematic Reviews and Meta-Analyses (PRISMA) guidelines. The paper analyzes the contribution, advantages, and limitations of each category and provides recommendations for future work. Based on the review, several recommendations for future work are provided, including the development of hybrid models that combine different optimization techniques, the incorporation of risk management into optimization models, and the use of advanced data analytics techniques to improve the accuracy of optimization models. Overall, this paper provides an up-to-date comprehensive review of the time-cost optimization models used in construction management and offers valuable insights for researchers and practitioners in this field. The findings of this review can be used to guide future research and improve the effectiveness of optimization models for construction projects. [ABSTRACT FROM AUTHOR]

As a classical combinatorial optimization problem, the traveling salesman problem (TSP) has been extensively investigated in the fields of Artificial Intelligence and Operations Research. Due to being NP-complete, it is still rather challenging to solve both effectively and efficiently. Because of its high theoretical significance and wide practical applications, great effort has been undertaken to solve it from the point of view of intelligent search. In this paper, we propose a two-stage probe-based search optimization algorithm for solving both symmetric and asymmetric TSPs through the stages of route development and a self-escape mechanism. Specifically, in the first stage, a reasonable proportion threshold filter of potential basis probes or partial routes is set up at each step during the complete route development process. In this way, the poor basis probes with longer routes are filtered out automatically. Moreover, four local augmentation operators are further employed to improve these potential basis probes at each step. In the second stage, a self-escape mechanism or operation is further implemented on the obtained complete routes to prevent the probe-based search from being trapped in a locally optimal solution. The experimental results on a collection of benchmark TSP datasets demonstrate that our proposed algorithm is more effective than other state-of-the-art optimization algorithms. In fact, it achieves the best-known TSP benchmark solutions in many datasets, while, in certain cases, it even generates solutions that are better than the best-known TSP benchmark solutions. [ABSTRACT FROM AUTHOR]

A given special case of NP-complete scheduling problem can be approximated by solving a special case of similar problem with the same precedence graph. We construct a metric space over a set of special cases of this problem and consider the statistical relationship between distance between a pair of special cases of the under consideration and the average error of the approximated solution. Sethi, Gabow, Coffman's and Fujii's algorithms for this problem are used. It is shown that the absolute and the relative error of the objective function decreases over the density of a graph with a fixed number of jobs. In general case, relative non-zero error value increases with the number of jobs. [ABSTRACT FROM AUTHOR]

Computational methods for rostering and personnel scheduling has been a subject of continued research and commercial interest since the 1950s. This annotated bibliography puts together a comprehensive collection of some 700 references in this area, focusing mainly on algorithms for generating rosters and personnel schedules but also covering related areas such as workforce planning and estimating staffing requirements. We classify these papers according to the type of problem addressed, the application areas covered and the methods used. In addition, a short summary is provided for each paper. [ABSTRACT FROM AUTHOR]

In this paper, we analyze two types of refutations for Unit Two Variable Per Inequality (UTVPI) constraints. A UTVPI constraint is a linear inequality of the form: $a_{i}\cdot x_{i}+a_{j} \cdot x_{j} \le b_{k}$ , where $a_{i},a_{j}\in \{0,1,-1\}$ and $b_{k} \in \mathbb{Z}$. A conjunction of such constraints is called a UTVPI constraint system (UCS) and can be represented in matrix form as: ${\bf A \cdot x \le b}$. UTVPI constraints are used in many domains including operations research and program verification. We focus on two variants of read-once refutation (ROR). An ROR is a refutation in which each constraint is used at most once. A literal-once refutation (LOR), a more restrictive form of ROR, is a refutation in which each literal ( $x_i$ or $-x_i$) is used at most once. First, we examine the constraint-required read-once refutation (CROR) problem and the constraint-required literal-once refutation (CLOR) problem. In both of these problems, we are given a set of constraints that must be used in the refutation. RORs and LORs are incomplete since not every system of linear constraints is guaranteed to have such a refutation. This is still true even when we restrict ourselves to UCSs. In this paper, we provide NC reductions between the CROR and CLOR problems in UCSs and the minimum weight perfect matching problem. The reductions used in this paper assume a CREW PRAM model of parallel computation. As a result, the reductions establish that, from the perspective of parallel algorithms, the CROR and CLOR problems in UCSs are equivalent to matching. In particular, if an NC algorithm exists for either of these problems, then there is an NC algorithm for matching. [ABSTRACT FROM AUTHOR]

The growing data have brought tremendous pressure for query processing and storage, so there are many studies that focus on using GPU to accelerate join operation, which is one of the most important operations in modern database systems. However, existing GPU acceleration join operation researches are not very suitable for the join operation on big data. Based on this, this paper speeds up nested loop join, hash join and theta join, combining Hadoop with GPU, which is also the first to use GPU to accelerate theta join. At the same time, after the data pre-filtering and pre-processing, using MapReduce and HDFS in Hadoop proposed in this paper, the larger data table can be handled, compared to existing GPU acceleration methods. Also with MapReduce in Hadoop, the algorithm proposed in this paper can estimate the number of results more accurately and allocate the appropriate storage space without unnecessary costs, making it more efficient. Experimental results show that comparing with GPU-based approach without Hadoop, our approach increases the speed by 1.5–2 times, and comparing with the Hadoop-based approaches without GPU, our approach increases the speed by 1.3–2 times. [ABSTRACT FROM AUTHOR]

Constraint programming has roots in logic programming, where a model has both a declarative and a procedural interpretation. A model is declarative because its statements can be read as logical propositions that describe the problem, and it is procedural because the statements can be processed as instructions for how to find a solution. To make constraint programming material to practical problems one needs propagation algorithms that are both viable and proficient. The most incredible propagation algorithm for the alldifferent constraint, i.e. the one getting hyper-circular segment consistency, is to be sure extremely productive. The reason is that we can apply matching hypothesis from operations research. Likewise for the symmetric alldifferent constraint and the weighted alldifferent constraint powerful and effective propagation algorithms exist, again dependent on techniques from operations research. From this paper we show that some time alldifferent constraint is more easy way to solve the MIP. For this we will choose an auction strategy by which a company get more revenue. Despite this considerable progress, there remains great potential for further integration, with the concomitant improvement in both modeling and solution method. [ABSTRACT FROM AUTHOR]

The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.

Copyright of Exacta is the property of Exacta - Engenharia de Producao and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The article presents information on minimum score separation, an open combinatorial problem associated with the cutting stock problem. An additional constraint is imposed on the software for the cutting stock problem in the paper and related industries. The algorithm for solving the cutting stock problem creates a large list of candidate patterns and then solves the associated mixed-integer programme. Typically, the list of candidate patterns is in the many hundreds, whereas only a few, in the low tens, will be used in the final solution.

Evolutionary algorithms, a form of meta-heuristic, have been successfully applied to a number of classes of complex combinatorial problems such as the well-studied travelling salesman problem, bin packing problems, etc. They have provided a method other than an exact solution that will, within a reasonable execution time, provide either optimal or near optimal results. In many cases near optimal results are acceptable and the additional resources that may be required to provide exact optimal results prove uneconomical. The class of project scheduling problems (PSP) exhibit a similar type of complexity to the previous mentioned problems, also being NP-hard, and therefore would benefit from solution via meta-heuristic rather than exhaustive search. Improvement to a project schedule in terms of total duration or resource utilisation can be of major financial advantage and therefore near optimal solution via evolutionary techniques should be considered highly applicable. In preparation for further research this paper reviews the application of evolutionary algorithms to the PSP to date extending previous reviews in this area by also encompassing the study of PSP using the design structure matrix. In order to better examine the coverage of this research, this paper also utilises the PSP classification system proposed by (Herroelen, W., Demeulemeester, E. and de Reyck, B., A note on the paper ‘Resource-constrained project scheduling: notation, classification, models and methods’ by Brucker et al., Euro. J. Op. Res., 2001, 128, 679–688.) to identify the problems being studied in each application and to identify the areas lacking in research. The paper concludes with an examination of areas that in the opinion of the authors would particularly benefit from further research. [ABSTRACT FROM AUTHOR]

Many dominance relations have been established in the literature for scheduling problems where they are mainly used in implicit enumeration techniques to further reduce the search space for finding an optimal solution. In this paper, we propose a novel method for discovering dominance relations for scheduling problems. We discover dominance relations by using an evolutionary algorithm. The proposed method of empirically discovering dominance relations can be used for any scheduling problem. After the description of the method, we apply it to a specific scheduling problem. The specific problem is the multimedia data objects scheduling problem for WWW applications which can be modelled as the two-machine flowshop problem of minimizing maximum lateness with separate setup times. The performances of the dominance relations obtained by the proposed method as well as the existing four dominance relations in literature are analysed. The results of the computational experiments show that the proposed method is quite efficient. [ABSTRACT FROM AUTHOR]

Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution's cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems. [ABSTRACT FROM AUTHOR]

The resource-constrained project scheduling problem (RCPSP) has received wide attention. In this paper, an activity-list-based nested partitions algorithm (ALNP) is developed for solving the RCPSP and a P-ALNP is proposed to improve ALNP with local adjustment. In the algorithms, to improve the search efficiency, a partial double justification is employed as local search mechanism. The computational experiments on the PSPLIB and analysis on robustness of the algorithms show that ALNP outperforms the traditional serial scheduling scheme for solving the large-scale, complex RCPSPs, and P-ALNP can improve ALNP and obtain better results. P-ALNP is a competitive algorithm for solving the RCPSP. [ABSTRACT FROM AUTHOR]

The uncapacitated transportation problem (UTP) deals with minimizing the transportation costs related to the delivery of a homogeneous product from multi-suppliers to multi-consumers. The application of the UTP can be extended to other areas of operations research, including inventory control, personnel assignment, signature matching, product distribution with uncertainty, multi-period production and inventory planning, employment scheduling, and cash management. Such a UTP with interval-defined demands and suppliers capacities (UTPIDS) is investigated in this paper. In UTPIDS, the demands and suppliers capacities may not be known exactly but vary within an interval due to variation in the economic conditions of the global economy. Following the variation, the minimal total cost of the transportation can also be varied within an interval and thus, the cost bounds can be obtained. Here, although the lower bound solution can be attained methodologically, the correct estimation of the worst case realization (the exact upper bound) on the minimal total transportation cost of the UTPIDS is an NP-hard problem. So, the decision-makers seek for minimizing the transportation costs and they are interested in the estimation of the worst case realization on these minimal costs for better decision making especially, for proper investment and return. In literature very few approaches are available to find this estimation of the worst case realization with some shortcomings. First, we demonstrate that the available heuristic methods fail to obtain the correct estimation of the worst case realization always. In this situation, development of a better heuristic method to find the better near optimal estimation of the worst case realization on the minimal total costs of the UTPIDS is desirable. Then this paper provides a new polynomial time algorithm that runs in O (N2) time (N, higher of the numbers of source and destination nodes) for better estimation. A comparative assessment on solutions of available benchmark instances, some randomly generated numerical example problems and a real-world application shows promising performance of the current technique. So, our new finding would definitely be benefited to practitioners, academics and decision makers who deal with such type of decision making instances. [ABSTRACT FROM AUTHOR]

This paper considers the scheduling problem faced by a manufacturer who is required to conform strictly to previously agreed due dates (or delivery dates). Penalties are assessed in the event that the product or service delivered is not yet complete. The model allows for a disruption cost each time a delivery is made. The objective is to minimize a total penalty function based on the announced due dates, the tardiness of each job and the number of distinct due dates used. The problem is solved by an efficient algorithm which simultaneously finds optimal solutions for the number of due dates to use, the specifications of those due dates and the order processing for the jobs. A numerical example demonstrates the operation of the algorithm. [ABSTRACT FROM AUTHOR]

With the transformation from traditional manufacturing to intelligent manufacturing, customer-oriented personalized customization has gradually become the main mode of production. Interactive algorithms determine the pros and cons of the solution via customers which can make customers better participants in the customization process. However, if the population size is expanded and the number of evolutionary iterations is too high, frequent interactions are likely to cause customer fatigue. This paper proposes an adaptive interactive artificial immune algorithm based on improved hierarchical clustering. This algorithm uses the improved hierarchical clustering algorithm to optimize generation of the initial antibodies and applies the affinity calculation method based on customer intention, adaptive crossover and mutation operators, and a multisolution reservation method based on hybrid selection strategy to the artificial immune algorithm. Via empirical research on the customized operational data of wheel hubs, the proposed method effectively solves the problem of customer fatigue, significantly improves the convergence speed of the algorithm and reduces the time cost. [ABSTRACT FROM AUTHOR]

The p-center problem has been the subject of interest in the operational research for a long time. It has been well-known since the middle of the previous century. During the last decade, an extension of the problem, known as the p-next center problem, has been defined in order to handle unexpected incidents that can disable the centers. There are only a few papers and algorithms that address the aforementioned problem and therefore we introduce a new algorithm for solving the p-next center problem based on the Variable Neighborhood Search Method. The proposed algorithm was tested on a set of test instances already known in the literature, and the results show that it returns an optimal or at least near-optimal solution to the problem in a reasonable amount of time. Compared to existing algorithms, it has been shown that the proposed algorithm finds the best known or better solutions. [ABSTRACT FROM AUTHOR]