In the last decade, market pressures for greater variety of products forced a gradual shift from continuous manufacturing to batch manufacturing in various industries. Consequently batch scheduling problems have attracted the attention of researchers in production and operations management. This thesis addresses the scheduling of parallel non-identical batch processors in the presence of dynamic job arrivals, incompatible job-families and non-identical job sizes. This problem abstracts the scheduling of heat-treatment furnace operations of castings in a steel foundry. The problem is of considerable interest in this sector as a large proportion of the total production time is spent in heat treatment processing. This problem is also encountered in other industrial settings such as burn-in operation in the final testing stage of semiconductor manufacturing, and manufacturing of steel, ceramics, aircraft parts, footwear, etc. A detailed literature review and personal communications with experts revealed that this class of batch scheduling problems have not been addressed hitherto. A major concern in the management of foundries is to maximize throughput and reduce flow time and work-in-process inventories. Therefore we have chosen the primary scheduling objective to be the utilization of batch processors and as secondary objectives the minimization of overall flow time and weighted average waiting time per job. This formulation can be considered as an extension of problems studied by DOBSON AND NAMBINADOM (1992), UZSOY (1995), ZEE et a/. (1997) and MEHTA AND UZSOY (1998). Our effort to carefully catalogue the large number of variants of deterministic batch scheduling problems led us to the development of a taxonomy and notation. Not surprisingly, we are able to show that our problem is NP-hard and is therefore in the company of many scheduling problems that are difficult to solve. Initially two heuristic algorithms, one a mathematical programming based heuristic algorithm (MPHA) and the other a greedy heuristic algorithm were developed. Due to the computational overheads in the implementation of MPHA when compared with the greedy heuristic, we chose to focus on the latter as the primary scheduling methodology. Preliminary experimentation led us to the observation that the performance of greedy heuristics depends critically on the selection of job-families. So eight variants of the greedy heuristic that differ mainly in the decision on "job-family selection" were proposed. These eight heuristics are basically two sets {Al, A2, A3, A4} and the modified (MAI, MA2, MA3, MA4}, which differ only on how the "job-family" index, weighted shortest processing time, is computed. For evaluating the performance of the eight heuristics, computational experiments were carried out. The analysis of the experimental data is presented in two perspectives. The goal of the first perspective was to evaluate the absolute quality of the solutions obtained by the proposed heuristic algorithms when compared with estimated optimal solutions. The second perspective was to compare the relative performance of the proposed heuristics. The test problems generated were designed to reflect real-world scheduling problems that we have observed in the steel-casting industry. Three important problem parameters for the test set generation are the number of jobs [n], job-priority [P], and job-family [F]. We considered 5 different levels for n, 2 different levels for P and 2 different levels for F. The test set reflects (i) the size of the jobs vary uniformly (ii) there are two batch processors and (iii) five incompatible job-families with different processing times. 15 problem instances were generated for each level of (n, P, and F). Out of many procedures available in the literature for estimating optimal value for combinatorial optimization problems, we used the procedure based on Weibull distribution as discussed in Rardin and Uzsoy (2001). For each problem instance of the randomly generated 300 problem instances, 15 feasible solutions (i.e., the average utilization of batch processors (AUBP)) were obtained using "random decision rule for first two stages and using a "best-fit heuristic' for the last stage of the scheduling problem. These 15 feasible solutions were used to estimate the optimal value. The generated 15 feasible solutions are expected to provide the estimated optimal value of the problem instance with a very high probability. Both average performance and worst-case performance of the heuristics indicated that, the heuristic algorithms A3 and A4, on the average yielded better utilization than the estimated optimal value. This indicates that the Weibull-based technique may have yielded conservative estimates of the optimal value. Further, the other heuristic algorithms found inferior solutions when compared with the estimated optimal value. But the deviations were very small. From this, we may infer that all the proposed heuristic algorithms are acceptable. The relative evaluation of heuristics was in terms of both computational effort and the quality of the solution. For the heuristics, it was clear that the computational burden is low enough on the average to run all the proposed heuristics on each problem instance and select the best solution. Also, it is observed that any algorithm from the first set of {Al, A2, A3, and A4} takes more computational time than any one from the second set {MAI, MA2, MA3, and MA4}. Regarding solution quality, the following inferences were made: ٭ In general the heuristic algorithms are sensitive to the choice of problem factors with respect to all the scheduling objectives. ٭ The three algorithms A3, MA4 and MAI are observed to be superior with respect to the scheduling objectives: maximizing average utilization of batch processors (AUBP), minimization of overall flow time (OFT) and minimizing weighted average waiting time (WAWT) respectively. Further, the heuristic algorithm MAI turns out to be the best choice if we trade-off all three objectives AUBP, OFT and WAWT. Finally we carried out simple sensitivity analyses experiments in order to understand the influence of some parameters of the scheduling on the performance of the heuristic algorithms. These were related to one at a time changes in (1) job-size distribution, (2) capacities of batch processors and (3) processing time of job-families. From the analyses it appears that there is an influence of changes in these input parameters. The results of the sensitivity analyses can be used to guide the selection of a heuristic for a particular combination of input parameters. For example, if we have to pick a single heuristic algorithm, then MAI is the best choice when considering the performance and the robustness indicated by the sensitivity analysis. In summary, this thesis examined a problem arising in the scheduling of heat-treatment operations in the steel-casting industry. This problem was abstracted to a class of deterministic batch scheduling problems. We analyzed the computational complexity of this problem and showed that it is NP-hard and therefore unlikely to admit a scalable exact method. Eight variants of a fast greedy heuristic were designed to solve the scheduling problem of interest. Extensive computational experiments were carried out to compare the performance of the heuristics with estimated optimal values (using the Weibull technique) and also for relative effectiveness and this showed that the heuristics are capable of consistently obtaining near-estimated) optimal solutions with very low computational burden for the solution of large scale problems. Finally, a comprehensive sensitivity analysis was carried out to study the influence of a few parameters, by changing them one at a time, on the performance of the heuristic algorithms. This type of analysis gives users some confidence in the robustness of the proposed heuristics.

Rapporten presenterar ett examensarbete vid Kungliga Tekniska Högskolan, utfört på ett företag i skylttillverkningsindustrin. Syftet med examensarbetet är att undersöka om produktionen på det uppdragsgivande företaget kan effektiviseras genom att ersätta ett manuellt arbetsmoment med en automatiserad lösning i form av en mjukvara. Det undersöks även om, och i sådant fall hur stora förbättringar som kan göras i processen sett till ekonomisk, ekologisk och social hållbarhet. Genom att undersöka marknadens utbud av mjukvaror för nesting och jämföra mjukvarornas egenskaper mot definierade krav kunde en handfull mjukvaror konstateras vara relevanta. Testprogramvaror begärdes för dessa, och i de fall de erhölls så testades mjukvarorna på rådata från projekt som företaget tidigare tillverkat i syfte att jämföra resultaten. Skillnaderna i resultat beräknades och jämfördes med resultaten av det manuella arbetssättet. Det konstaterades att användning av den bäst presterande mjukvaran kan spara företaget i snitt 481 kronor per projekt i minskad material- och tidsåtgång. Vidare beräknades att företaget hade kunnat spara drygt 28 kg material på de fem projekten som tillverkades i aluminium, för vilka bara återvinningen hade kostat ca 2,25 kg koldioxidekvivalenter per projekt. Nyproduktionen av denna aluminium uppskattas motsvara mellan 16,6 – 36,2 kg koldioxidekvivalenter per projekt. / This paper presents a bachelors thesis at the Royal Institute of Technology, performed at a company in the sign manufacturing industry. The aim of the thesis is to investigate if the production at the company can be made more effective by replacing a part of the process that requires manual work with an automated solution in the form of a software. It is also investigated whether changes in the process can result in improvements in economical, ecological and social sustainability, and in that case the greatness of the improvements. By conducting market research of nesting software and comparing the properties of the software to pre-determined requirements, a handful of different software were considered potentially applicable. Software for testing were requested for these, and tests were conducted with those that were obtained. The tests were conducted on raw data from previously manufactured projects at the company in order to compare the results. The differences in results were calculated and compared with those of the manual process. It was concluded that the top performing software could render the company an average of 481 kronor saved per project in terms of time saved and material usage. Furthermore, calculations showed that the company could have saved over 28 kg worth of material for the five projects where aluminium was used. For these projects, the recycling of the aluminium would be equivalent to 2,25 kg carbon dioxide equivalents per kg, per project. The production of new aluminium for these projects would equate to an estimated 16,6 – 36,2 kg carbon dioxide equivalents per kg, per project.

Background: Sustainable organizational change has become one of the greatest challenges facing contemporary businesses. The metal manufacturing industry is important in the transition, due to its impact on global GDP and the climate. SMEs covers a large portion of the metal manufacturing industry, where their transformation is crucial as well. Problem: Despite the importance of sustainable change, there is limited research on how manufacturing SMEs can effectively manage a sustainable transformation. This gap necessitates elucidating the context of SMEs in sustainability, and exploring methods for sustainable change management within these organizations.  Purpose: The aim of this research is to explore sustainability and organizational change in the context of manufacturing SMEs, to provide a deeper understanding on how manufacturing SMEs can sustainably transform their business activities through adequate methods and processes. Method: This research takes on the philosophical position of critical realism and utilizes a qualitative, explorative, and inductive approach. Semi-structured interviews were conducted with ten managers from manufacturing SMEs. A thematic analysis was also adopted to extend the previous research.  Conclusion: Manufacturing SMEs adopt various sustainability activities, in line with the triple bottom line. They are also going towards a more formal approach for sustainability. Economic performance and sustainability go together for manufacturing SMEs, whereas more knowledge is connected to higher altruistic motivations and clear sustainability strategies. A combination of continuous incremental and transformational change is evident. This research found a six-step process for SMEs sustainable change management, elucidating their more flexible and adaptive culture alongside specific advantages and challenges. Their capabilities of learning and an informal culture facilitates fast decision-making and the continuous improvement of their practices, facilitating economic performance and sustainable change.