In this study, the two-dimensional cutting stock problem (2DCSP) is considered. This is a problem that occurs in the cutting of a number of smaller rectangular pieces or items from a set of large stock rectangles. It is assumed that the set of large objects is sufficient to accommodate all the small items. A heuristic procedure is developed to solve the two-dimensional single stock-size cutting stock problem (2DSSSCSP). This is the special case where the large rectangles are all of the same size. The major objective is to minimize waste and the number of stock sheets utilized. The heuristic procedures developed to solve the 2DSSSCSP are based on the generation of cutting pattern. The Wang algorithm and a specific commercial software package are made use of to generate these patterns. The commercial software was chosen from a set of commercial software packages available in the market. A combinatoric process is applied to generate sets of cutting patterns using the Wang algorithm and the commercial software. The generated cutting patterns are used to formulate an integer linear programming model which is solved using an optimization solver. Empirical experimentation is carried out to test the heuristic procedures using data obtained from both small and real world application problem instances. The results obtained shows that the heuristic procedures developed produce good quality results for both small and real life problem instances. It is quite clear that the heuristic procedure developed to solve the 2DSSSCSP produces cutting patterns which are acceptable in terms of waste generated and may offer useful alternatives to approaches currently available. Broadly stated, this study involves investigating available software (commercial) in order to assess, formulate and investigate methods to attempt to benchmark software systems and algorithms and to employ ways to enhance solutions obtained by using these software systems. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2011.

In this study, the two-dimensional cutting stock problem (2DCSP) is considered. This is a problem that occurs in the cutting of a number of smaller rectangular pieces or items from a set of large stock rectangles. It is assumed that the set of large objects is sufficient to accommodate all the small items. A heuristic procedure is developed to solve the two-dimensional single stock-size cutting stock problem (2DSSSCSP). This is the special case where the large rectangles are all of the same size. The major objective is to minimize waste and the number of stock sheets utilized. The heuristic procedures developed to solve the 2DSSSCSP are based on the generation of cutting pattern. The Wang algorithm and a specific commercial software package are made use of to generate these patterns. The commercial software was chosen from a set of commercial software packages available in the market. A combinatoric process is applied to generate sets of cutting patterns using the Wang algorithm and the commercial software. The generated cutting patterns are used to formulate an integer linear programming model which is solved using an optimization solver. Empirical experimentation is carried out to test the heuristic procedures using data obtained from both small and real world application problem instances. The results obtained shows that the heuristic procedures developed produce good quality results for both small and real life problem instances. It is quite clear that the heuristic procedure developed to solve the 2DSSSCSP produces cutting patterns which are acceptable in terms of waste generated and may offer useful alternatives to approaches currently available. Broadly stated, this study involves investigating available software (commercial) in order to assess, formulate and investigate methods to attempt to benchmark software systems and algorithms and to employ ways to enhance solutions obtained by using these software systems. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2011.

Ce travail porte sur la segmentation jointe d’un ensemble d’images dans un cadre bayésien.Le modèle proposé combine le processus de Dirichlet hiérarchique (HDP) et le champ de Potts.Ainsi, pour un groupe d’images, chacune est divisée en régions homogènes et les régions similaires entre images sont regroupées en classes. D’une part, grâce au HDP, il n’est pas nécessaire de définir a priori le nombre de régions par image et le nombre de classes, communes ou non.D’autre part, le champ de Potts assure une homogénéité spatiale. Les lois a priori et a posteriori en découlant sont complexes rendant impossible le calcul analytique d’estimateurs. Un algorithme de Gibbs est alors proposé pour générer des échantillons de la loi a posteriori. De plus,un algorithme de Swendsen-Wang généralisé est développé pour une meilleure exploration dela loi a posteriori. Enfin, un algorithme de Monte Carlo séquentiel a été défini pour l’estimation des hyperparamètres du modèle.Ces méthodes ont été évaluées sur des images-test et sur des images naturelles. Le choix de la meilleure partition se fait par minimisation d’un critère indépendant de la numérotation. Les performances de l’algorithme sont évaluées via des métriques connues en statistiques mais peu utilisées en segmentation d’image. / This work concerns the joint segmentation of a set images in a Bayesian framework. The proposed model combines the hierarchical Dirichlet process (HDP) and the Potts random field. Hence, for a set of images, each is divided into homogeneous regions and similar regions between images are grouped into classes. On the one hand, thanks to the HDP, it is not necessary to define a priori the number of regions per image and the number of classes, common or not.On the other hand, the Potts field ensures a spatial consistency. The arising a priori and a posteriori distributions are complex and makes it impossible to compute analytically estimators. A Gibbs algorithm is then proposed to generate samples of the distribution a posteriori. Moreover,a generalized Swendsen-Wang algorithm is developed for a better exploration of the a posteriori distribution. Finally, a sequential Monte Carlo sampler is defined for the estimation of the hyperparameters of the model.These methods have been evaluated on toy examples and natural images. The choice of the best partition is done by minimization of a numbering free criterion. The performance are assessed by metrics well-known in statistics but unused in image segmentation.