A Lagrangian relaxation approach to solve the second phase of the exam scheduling problem

The problem of scheduling final exams at a large university can be viewed as a three phase process. The first phase consists of grouping the exams into sets called exam blocks. The second phase deals with the assignment of exam blocks to exam days and the third phase consists of arranging the exam days and also arranging the blocks within days.In this paper, we present new integer programming formulations for the second phase of the scheduling problem. We present an integer program with a single objective of minimizing the number of students with two or more exams per day. We then present a Lagrangian relaxation based solution procedure to solve this problem. Further, we present a bicriterion integer programming formulation to minimize the number of students with two exams per day and the number of students with three exams per day. Finally, we present some computational experience using randomly generated problems as well as real world data obtained from the State University of New York at Buffalo.     

The effect of attending tutoring on course grades in Calculus I

Tutoring centres are common in universities in the United States, but there are few published studies that statistically examine the effects of tutoring on student success. This study utilizes multiple regression analysis to model the effect of tutoring attendance on final course grades in Calculus I. Our model predicted that every three visits to the tutoring centre is correlated with an increase of a students’ course grade by one per cent, after controlling for prior academic ability. We also found that for lower-achieving students, attending tutoring had a greater impact on final grades.     

The equilibrium generalized assignment problem and genetic algorithm

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.     

Coordinating Numeric and Linear Units: Elementary Students’ Strategies for Locating Whole Numbers on the Number Line

Two investigations of fifth graders’ strategies for locating whole numbers on number lines revealed patterns in students’ coordination of numeric and linear units. In Study 1, we investigated the effects of context on students’ placements of three numbers on an open number line. For one group (n?=?24), the line was presented in a thematic context as a “race course,” and, for a second group (n?=?24), the line was presented as a conventional number line. Most students in both groups placed consecutive whole numbers at appropriate linear distances, but the thematic context group was more likely to place nonconsecutive whole numbers at appropriate linear distances. In Study 2 (n?=?24), students placed numbers on lines marked with two numbers. Most students placed a third number appropriately when the marked numbers were consecutive whole numbers, but not when the labeled numbers were nonconsecutive whole numbers. The findings reveal fifth graders’ conceptual difficulties in coordinating numeric and linear units on the number line and a thematic context that can support this coordination.     

Correcting grade deflation caused by multiple-choice scoring

In a study involving three sections of 181 pre-calculus students at a four-year college, partial credit scoring on multiple-choice questions was examined over an entire semester. Questions were constructed by experienced teachers to pose carefully designed, incorrect alternatives, many of which implicitly suggested varying degrees of partial knowledge or understanding. Computing students' course grades based solely on percentage correct scoring resulted in a course-wide GPA of 1.38. This seemed inconsistent with the fact that students were screened for entry into the course. To avert apparent grade deflation due to such right/wrong scoring, student scores were recomputed based on supplementing percentage correct scores with partial credit. This resulted in a course-wide increase in GPA to 1.92. Using that same letter grade distribution, and curving percentage correct averages to achieve the 1.92 GPA, it was found that 10% of the students were given different grades from those determined by the partial credit scoring. Regarding the efficacy of awarding partial credit points, it was found that partial credit by itself measured achievement of relevant mathematical skills that were missed by percentage correct scoring. Overall, grades determined by partial credit scoring seemed more reflective of both the quantity and quality of student knowledge than grades determined by either traditional percentage correct scoring or any corrective curving.     

Optimal observation network in geostatistics and underground hydrology

Mathematical models and algorithms for the optimal design of data collection for regionalized variables are presented. The topics considered subsume as a special case optimal drilling strategies in hydrology, the mining industries and other geostatistical applications. In these disciplines an optimal design is a critical consideration since data, can only be obtained through an expensive drilling process.The methods given here are based on the theory of regionalized variables and of kriging. The basis of the methods for locating a single additional data point, and for locating multiple points, is the theory of minimizing uncertainty in parameter estimation. That is, the possible locations of additional points must be determined on the basis of surface analysis with respect to the projected costs of obtaining this data.After a summary of basic kriging techniques, four models are discussed. The first deals with the optimal location problem for a single experimental point, and the second, third and fourth models pertain to the case of multiple additional points. (Unfortunately the repeated application of the single-point model leads only to approximations of the global optima, since the global optima are usually unobtainable as a simple sum of the partial optima.) In the second model, an optimal regular observation network is to be designed to minimize the uncertainty of the estimation process subject to either the given number of additional data, or an upper bound for the cost of the additional data. In the fourth model, the number or cost of additional points is minimized subject to bounded uncertainty conditions. Finally, a numerical example will be used to illustrate the models and algorithms.     

Successive Pursuit with a Bounded Detection Domain

We study a coplanar model of the successive pursuit of two evaders with unlimited turn rates of the players and a bounded detection domain of a pursuer. Involved in catching the first evader, the pursuer may lose sight of the other. In this case, it must search later for the lost evader in the plane. We describe two guaranteed pursuit strategies obtained as solutions of differential games. Both strategies include a two-stage strategy to shorten to a specified quantity the distance to the nearer evader, and a two-stage strategy to search and capture the other.The strategies are distinguished by their search plans. First, coalition is pursued as a whole. Then, to minimize an uncertainty index, the pursuer approaches the first evader using the strategy of successive pursuit with the unmoved second evader at its last observed position. Subsequently, the pursuer moves directly to that position of the second evader, or according to the more complex plan, alternates between traversing a straight line and arcs of logarithmic spirals. After detection, the remaining evader is captured with the use of a simple pursuit strategy.The barriers fit the strategies. We call them approximate, since they bound the states where the pursuer succeeds with the guaranteed (but not optimal as in the case of ordinary barriers) strategies. These barriers are surfaces of constant values of a special game of degree. The more complex search plan secures a wider winning area.Geometrical interpretations and some numerical results for a set of parameters of the game are provided.     

A unified approach for scheduling with convex resource consumption functions using positional penalties

We provide a unified model for solving single machine scheduling problems with controllable processing times in polynomial time using positional penalties. We show how this unified model can be useful in solving three different groups of scheduling problems. The first group includes four different due date assignment problems to minimize an objective function which includes costs for earliness, tardiness, due date assignment, makespan and total resource consumption. The second group includes three different due date assignment problems to minimize an objective function which includes the weighted number of tardy jobs, due date assignment costs, makespan and total resource consumption costs. The third group includes various scheduling problems which do not involve due date assignment decisions. We show that each of the problems from the first and the third groups can be reduced to a special case of our unified model and thus can be solved in O(n³)$O(n^3)$ time. Furthermore, we show how the unified model can be used repeatedly as a subroutine to solve all problems from the second group in O(n⁴)$O(n^4)$ time. In addition, we also show that faster algorithms exist for several special cases.     

Efficient heuristics for Median Cycle Problems

This article proposes a number of efficient heuristics for two versions of the Median Cycle Problem. In both versions, the aim is to construct a simple cycle containing a subset of the vertices of a mixed graph. In the first version, the objective is to minimize the cost of the cycle and the cost of assigning vertices not on the cycle to the nearest vertex on the cycle. In the second version, the objective is to minimize the cost of the cycle subject to an upper bound on the total assignment cost. Two heuristics are developed. The first, called the multistart greedy add heuristic, is composed of two main phases. In the first phase, a cycle composed of a limited number of randomly chosen vertices is constructed and augmented by iteratively adding the vertex yielding the largest cost reduction until either no further reduction is possible (for the first version) or the assignment cost is below the upper bound (for the second version). The second phase applies a number of improvement routines. The second heuristic is a random keys evolutionary algorithm. Computational results on a number of benchmark test instances show that the proposed heuristics are highly efficient for both versions of the problem, and superior to the only other available heuristic for these two versions of the problem.     

Integrated location and two-echelon inventory network design under uncertainty

In this paper, we propose a two-stage stochastic model to address the design of an integrated location and two-echelon inventory network under uncertainty. The central issue in this problem is to design and operate an effective and efficient multi-echelon supply chain distribution network and to minimize the expected system-wide cost of warehouse location, the allocation of warehouses to retailers, transportation, and two-echelon inventory over an infinite planning horizon. We structure this problem as a two-stage nonlinear discrete optimization problem. The first stage decides the warehouses to open and the second decides the warehouse-retailer assignments and two-echelon inventory replenishment strategies. Our modeling strategy incorporates various probable scenarios in the integrated multi-echelon supply chain distribution network design to identify solutions that minimize the first stage costs plus the expected second stage costs. The two-echelon inventory cost considerations result in a nonlinear objective which we linearize with an exponential number of variables. We solve the problem using column generation. Our computational study indicates that our approach can solve practical problems of moderate-size with up to twenty warehouse candidate locations, eighty retailers, and ten scenarios efficiently.     

Variation of student numerical and figural reasoning approaches by pattern generalization type,strategy use and grade level

This paper explored variation of student numerical and figural reasoning approaches across different pattern generalization types and across grade level. An instrument was designed for this purpose. The instrument was given to a sample of 1232 students from grades 4 to 11 from five schools in Lebanon. Analysis of data showed that the numerical reasoning approach seems to be more dominant than the figural reasoning approach for the near and far pattern generalization types but not for the immediate generalization type. The findings showed that for the recursive strategy, the numerical reasoning approach seems to be more dominant than the figural reasoning approach for each of the three pattern generalization types. However, the figural reasoning approach seems to be more dominant than the numerical reasoning approach for the functional strategy, for each generalization type. The findings also showed that the numerical reasoning was more dominant than the figural reasoning in lower grade levels (grades 4 and 5) for each generalization type. In contrast, the figural reasoning became more dominant than the numerical reasoning in the upper grade levels (grades 10 and 11).     

The Examination Where the Student Asks the Question

The Examination where the Student Asks the Questions (ESAQ) is an innovative, system-oriented teaching/evaluation strategy ideated, developed and successfully implemented by the author, initially within the teaching of freshman chemistry (general and organic) in a four-year college. It constitutes a reflective, multidimensional response to the urgent need for effective teaching and evaluation strategies which will foster question asking, and higher order cognitive skills (HOCS). Such strategies are, ideally, relevant, challenging, and compatible with the new goals of science teaching and student performance evaluation. The core element of the ESAQ is a prearranged oral examination in which the course professor is examined by students, using home-prepared, written questions. Our experience suggests that the ESAQ can be creatively adopted and successfully implemented in different contexts of science teaching worldwide and would benefit both educators and students. The increase in the HOCS capacity of students is attainable.     

Representational disfluency in algebra: evidence from student gestures and speech

In this investigation, we analyzed US middle school students’ (grades 6–8) gestures and speech during interviews to understand students’ reasoning while interpreting quantitative patterns represented by Cartesian graphs. We studied students’ representational fluency, defined as their abilities to work within and translate among representations. While students translated across representations to address task demands, they also translated to a different representation when reaching an impasse, where the initial representation could not be used to answer a task. During these impasse events, which we call representational disfluencies, three categories of behavior were observed. Some students perceived the graph to be bounded by its physical and numerical limits, and these students were categorized as physically grounded. A second, related, disfluency was categorized as spatially grounded. Students who were classified as spatially grounded exhibited a bounded view of the graph that limited their ability to make far predictions until they physically altered the spatial configuration of the graph by rescaling or extending the axes. Finally, students who recovered from one or more of these disfluencies by translating the quantitative information to alternative but equivalent representations (i.e., exhibiting representational fluency), while retaining the connection back to the linear pattern as graphed, were categorized as interpretatively grounded. Understanding the causes and varieties of representational fluency and disfluency contributes directly to our understanding of mathematics knowledge, learning and adaptive forms of reasoning. These findings also provide implications for mathematics instruction and assessment.     

The construction of numerical integration rules of degree three for product regions

Numerical integration formulas in n-dimensional Euclidean space of degree three are discussed. In this paper, for the product regions a method is presented to construct numerical integration formulas of degree three with 2n real points and positive weights. The presented problem is a little different from those dealt with by other authors. All the corresponding one-dimensional integrals can be different from each other and they are also nonsymmetrical. In this paper an n-dimensional numerical integration problem is turned into n one-dimensional moment problems, which simplifies the construction process. Some explicit numerical formulas are given. Furthermore, a more generalized numerical integration problem is considered, which will shed light on the final solution to the third degree numerical integration problem.     

The role of prior knowledge in the development of strategy flexibility: the case of computational estimation

The ability to estimate is a fundamental real-world skill; it allows students to check the reasonableness of answers found through other means, and it can help students develop a better understanding of place value, mathematical operations, and general number sense. Flexibility in the use of strategies is particularly critical in computational estimation. The ability to perform complex calculations mentally is cognitively challenging for many students; thus, it is important to have a broad repertoire of estimation strategies and to select the most appropriate strategy for a given problem. In this paper, we consider the role of students’ prior knowledge of estimation strategies in the effectiveness of interventions designed to promote strategy flexibility across two recent studies. In the first, 65 fifth graders began the study as fluent users of one strategy for computing mental estimates to multi-digit multiplication problems such as 17 × 41. In the second, 157 fifth and sixth graders began the study with moderate to low prior knowledge of strategies for computing mental estimates. Results indicated that students’ fluency with estimation strategies had an impact on which strategies they adopted. Students who exhibited high fluency at pretest were more likely to increase use of estimation strategies that led to more accurate estimates, while students with less fluency adopted strategies that were easiest to implement. Our results suggest that both the ease and accuracy of strategies as well as students’ fluency with strategies are all important factors in the development of strategy flexibility.     

Extensions of the sequential stochastic assignment problem

The sequential stochastic assignment problem (SSAP) allocates N workers to N IID sequentially arriving tasks so as to maximize the expected total reward. This paper studies two extensions of the SSAP. The first one assumes that the values of any two consecutive tasks are dependent on each other while the exact number of tasks to arrive is unknown until after the final arrival. The second extension generalizes the first one by assuming that the number of workers is also random. Optimal assignment policies for both problems are derived and proven to have the same threshold structure as the optimal policy of the SSAP.     

Stochastic optimal control of internal hierarchical labor markets

This paper develops an optimal control model for a graded manpower system where the demand for manpower is uncertain. The organization's objective is to minimize the discounted costs of operating the manpower system, including excess demand costs. The stock of workers in various grades can be adjusted in two ways. The first method is outside hiring flows, which is the usual control variable used in previous research. The second method is to control the transition rates between grades of the hierarchy, an instrument not previously studied. Incorporating the transition rates into the control variables creates time lags in the control process. The resulting problem is solved numerically using an approximation for the time-lagged control variables. The numerical example is based on the Air Force officer hierarchy. The model is used to examine such issues as the desirability of granting tenure to workers who are not promoted to the highest grade and the effects of length-of-service and demand uncertainty on manpower policy.     

The stochastic economic lot sizing problem for non-stop multi-grade production with sequence-restricted setup changeovers

We study a variant of the stochastic economic lot scheduling problem (SELSP) encountered in process industries, in which a single production facility must produce several different grades of a family of products to meet random stationary demand for each grade from a common finished-goods (FG) inventory buffer that has limited storage capacity. When the facility is set up to produce a particular grade, the only allowable changeovers are from that grade to the next lower or higher grade. Raw material is always available, and the production facility produces continuously at a constant rate even during changeover transitions. All changeover times are constant and equal to each other, and demand that cannot be satisfied directly from inventory is lost. There is a changeover cost per changeover occasion, a spill-over cost per unit of product in excess whenever there is not enough space in the FG buffer to store the produced grade, and a lost-sales cost per unit short whenever there is not enough FG inventory to satisfy the demand. We model the SELSP as a discrete-time Markov decision process (MDP), where in each time period the decision is whether to initiate a changeover to a neighboring grade or keep the set up of the production facility unchanged, based on the current state of the system, which is defined by the current set up of the facility and the FG inventory levels of all the grades. The goal is to minimize the (long-run) expected average cost per period. For problems with more than three grades, we develop a heuristic solution procedure which is based on decomposing the original multi-grade problem into several 3-grade MDP sub-problems, numerically solving each sub-problem using value iteration, and constructing the final policy for the original problem by combining parts of the optimal policies of the sub-problems. We present numerical results for problem examples with 2–5 grades. For the 2- and 3-grade examples, we numerically solve the exact MDP problem using value iteration to obtain insights into the structure of the optimal changeover policy. For the 4- and 5-grade examples, we compare the performance of the decomposition-based heuristic (DBH) solution procedure against that obtained by numerically solving the exact problem. We also compare the performance of the DBH method against the performance of three simpler parameterized heuristics. Finally, we compare the performance of the DBH and the exact solution procedures for the case where the FG inventory storage consists of a number of separate general-purpose silos capable of storing any grade as long as it is not mixed with any other grade.     

Complexity results on restricted instances of a paint shop problem for words

We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of its letters such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters.This is a special case of the paint shop problem for words, which was previously shown to be NP-complete. We show that this special case is also NP-complete and even APX-hard. Furthermore, derive lower bounds for this problem and discuss a transformation into matroid theory enabling us to solve some specific instances within polynomial time.     

Understanding the concepts of proportion and ratio among grade nine students in Malaysia

The purpose of the study was to investigate the concepts of ratio and proportion constructed by grade nine students by investigating grade nine students proportional reasoning schemes and procedures on three types of tasks: missing value, numerical comparison and qualitative reasoning. Comparisons among the different categories were made and the strategies used in solving these problems were identified. The relationship between student grades on a national examination and their knowledge of proportional reasoning was determined. The results of the quantitative analysis indicated that students performed generally well on the missing value tasks but their scores on the numerical comparison and qualitative tasks were much lower. The results indicate that only a small percentage of students who did well on the national exams were able to solve complex proportional problems and the grades obtained were not indicative of their knowledge of ratio and proportion. The difficulty experienced by the ninth graders indicated that students frequently used additive reasoning, that is a comparison of two numbers by subtraction rather than division. It appears that students cannot begin to understand the functional and scalar relationship inherent in a proportion until they first develop multiplicative reasoning.