Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Online and Offline Gaming as Support for English Education in Swedish Upper Elementary Schools with Focus on Reading Comprehension Online and Offline Gaming as Support for English Education in Swedish Upper Elementary Schools with Focus on Reading Comprehension : A literature review about online and offline gaming as a resource for developing English reading comprehension in Swedish schools in year 4-6

The aim of this degree thesis is to see what research says about the use of computer and video games to support upper elementary pupils’ development in English reading comprehension in Swedish schools. Other goals are to see how online and offline gaming can be integrated in the Swedish schools and what attitudes teachers have towards gaming. The method used is a systematic literature review and the purpose is to analyze chosen articles and to find relevant content that answers the research questions. Five articles were chosen from different databases and were systematically analyzed in this thesis. The results show that online gaming as support for education can be rewarding for some upper elementary pupils in English learning. However, in English reading comprehension there is not much research found which means that more research needs to be made within this area. Moreover, involving online gaming in English language learning seems to be a challenge for teachers mostly because of their lack of knowledge about the subject, even though they are positive to gaming. The lack of knowledge about the subject could be altered with more education and courses in the area.