Solving Challenging Real-World Scheduling Problems

This work contains a series of studies on the optimization of three real-world scheduling problems, school timetabling, sports scheduling and staff scheduling. These challenging problems are solved to customer satisfaction using the proposed PEAST algorithm. The customer satisfaction refers to the fact that implementations of the algorithm are in industry use. The PEAST algorithm is a product of long-term research and development. The first version of it was introduced in 1998. This thesis is a result of a five-year development of the algorithm. One of the most valuable characteristics of the algorithm has proven to be the ability to solve a wide range of scheduling problems. It is likely that it can be tuned to tackle also a range of other combinatorial problems. The algorithm uses features from numerous different metaheuristics which is the main reason for its success. In addition, the implementation of the algorithm is fast enough for real-world use.

The spindle assembly checkpoint as a drug target - Novel small-molecule inhibitors of Aurora kinases

Cell division (mitosis) is a fundamental process in the life cycle of a cell. Equal distribution of chromosomes between the daughter cells is essential for the viability and well-being of an organism: loss of fidelity of cell division is a contributing factor in human cancer and also gives rise to miscarriages and genetic birth defects. For maintaining the proper chromosome number, a cell must carefully monitor cell division in order to detect and correct mistakes before they are translated into chromosomal imbalance. For this purpose an evolutionarily conserved mechanism termed the spindle assembly checkpoint (SAC) has evolved. The SAC comprises a complex network of proteins that relay and amplify mitosis-regulating signals created by assemblages called kinetochores (KTs). Importantly, minor defects in SAC signaling can cause loss or gain of individual chromosomes (aneuploidy) which promotes tumorigenesis while complete failure of SAC results in cell death. The latter event has raised interest in discovery of low molecular weight (LMW) compounds targeting the SAC that could be developed into new anti-cancer therapeutics. In this study, we performed a cell-based, phenotypic high-throughput screen (HTS) to identify novel LMW compounds that inhibit SAC function and result in loss of cancer cell viability. Altogether, we screened 65 000 compounds and identified eight that forced the cells prematurely out of mitosis. The flavonoids fisetin and eupatorin, as well as the synthetic compounds termed SACi2 and SACi4, were characterized in more detail utilizing versatile cell-based and biochemical assays. To identify the molecular targets of these SAC-suppressing compounds, we investigated the conditions in which SAC activity became abrogated. Eupatorin, SACi2 and SACi4 preferentially abolished the tensionsensitive arm of the SAC, whereas fisetin lowered also the SAC activity evoked by lack of attachments between microtubules (MTs) and KTs. Consistent with the abrogation of SAC in response to low tension, our data indicate that all four compounds inhibited the activity of Aurora B kinase. This essential mitotic protein is required for correction of erratic MT-KT attachments, normal SAC signaling and execution of cytokinesis. Furthermore, eupatorin, SACi2 and SACi4 also inhibited Aurora A kinase that controls the centrosome maturation and separation and formation of the mitotic spindle apparatus. In line with the established profound mitotic roles of Aurora kinases, these small compounds perturbed SAC function, caused spindle abnormalities, such as multi- and monopolarity and fragmentation of centrosomes, and resulted in polyploidy due to defects in cytokinesis. Moreover, the compounds dramatically reduced viability of cancer cells. Taken together, using a cell-based HTS we were able to identify new LMW compounds targeting the SAC. We demonstrated for the first time a novel function for flavonoids as cellular inhibitors of Aurora kinases. Collectively, our data support the concept that loss of mitotic fidelity due to a non-functional SAC can reduce the viability of cancer cells, a phenomenon that may possess therapeutic value and fuel development of new anti-cancer drugs.

Aging based maintenance and reinvestment scheduling of electric distribution

The maintenance of electric distribution network is a topical question for distribution system operators because of increasing significance of failure costs. In this dissertation the maintenance practices of the distribution system operators are analyzed and a theory for scheduling maintenance activities and reinvestment of distribution components is created. The scheduling is based on the deterioration of components and the increasing failure rates due to aging. The dynamic programming algorithm is used as a solving method to maintenance problem which is caused by the increasing failure rates of the network. The other impacts of network maintenance like environmental and regulation reasons are not included to the scope of this thesis. Further the tree trimming of the corridors and the major disturbance of the network are not included to the problem optimized in this thesis. For optimizing, four dynamic programming models are presented and the models are tested. Programming is made in VBA-language to the computer. For testing two different kinds of test networks are used. Because electric distribution system operators want to operate with bigger component groups, optimal timing for component groups is also analyzed. A maintenance software package is created to apply the presented theories in practice. An overview of the program is presented.

Scheduling of guarded command based models

Formal methods provide a means of reasoning about computer programs in order to prove correctness criteria. One subtype of formal methods is based on the weakest precondition predicate transformer semantics and uses guarded commands as the basic modelling construct. Examples of such formalisms are Action Systems and Event-B. Guarded commands can intuitively be understood as actions that may be triggered when an associated guard condition holds. Guarded commands whose guards hold are nondeterministically chosen for execution, but no further control flow is present by default. Such a modelling approach is convenient for proving correctness, and the Refinement Calculus allows for a stepwise development method. It also has a parallel interpretation facilitating development of concurrent software, and it is suitable for describing event-driven scenarios. However, for many application areas, the execution paradigm traditionally used comprises more explicit control flow, which constitutes an obstacle for using the above mentioned formal methods. In this thesis, we study how guarded command based modelling approaches can be conveniently and efficiently scheduled in different scenarios. We first focus on the modelling of trust for transactions in a social networking setting. Due to the event-based nature of the scenario, the use of guarded commands turns out to be relatively straightforward. We continue by studying modelling of concurrent software, with particular focus on compute-intensive scenarios. We go from theoretical considerations to the feasibility of implementation by evaluating the performance and scalability of executing a case study model in parallel using automatic scheduling performed by a dedicated scheduler. Finally, we propose a more explicit and non-centralised approach in which the flow of each task is controlled by a schedule of its own. The schedules are expressed in a dedicated scheduling language, and patterns assist the developer in proving correctness of the scheduled model with respect to the original one.

Improving internal performance of a company - Introducing employee empowerment via job redesign in Finnish small and medium sized enterprises

This bachelor's thesis is about to find out to what extent Finnish managers and small and medium sized organizations are willing and able to put employee empowerment into practice and what experiences they have got from employee empowerment as an approach towards job redesign. Some of the top enterprises in the world are known for their empowered employees as a single most important factor for their success and this thesis focuses on introducing the subject to Finnish managers and organizations to find out what benefits, barriers and other thoughts they have about the whole idea of empowered employees in Finnish organization culture. Most notable findings in this thesis are that Finnish managers do think that their organization's employees are capable to work efficiently if their job is extended and the organizations would perform better when right person's job is enriched and he/she is given more power to solve problems.

Esimies osaamisen mahdollistajana

Tämän pro gradu -tutkielman tavoitteena oli esitellä ja analysoida osaami-sen johtamista sekä tuottaa käytännön suosituksia Alko Oy:n myymälöiden lähiesimiehille heidän henkilökuntansa osaamisen kehittämiseksi. Tämän lisäksi tutkimuksessa pyrittiin kerätyn aineiston avulla luomaan ymmärrys siitä, miten osaamisen johtamiset keinot vaikuttavat asiakastyytyväisyyteen. Tutkimus toteutettiin vertailevana tapaustutkimuksena ja tutkimusaineistoa kerättiin sekä kvantitatiivisella että kvalitatiivisella tutkimusmenetelmällä. Kohdeyrityksen myyjille lähetettiin kyselylomake heidän esimiestensä osaamisen johtamisen toimista, ja kyselystä saadun tiedon syventämiseksi haastateltiin kahdeksaa myymäläpäällikköä osaamisen johtamisen teemoista. Tutkimuksen perusteella pystyttiin muodostaman käsitys siitä, mistä osaa-misen johtaminen koostuu ja miten paremman ja heikomman osaamisen omaavien myymälöiden esimiesten toimet eroavat toisistaan. Vastausten perusteella saatiin myös ymmärrys niistä osa-alueista, joita kohdeyrityksen esimiesten toiminnassa pitäisi pyrkiä kehittämään. Osaamisen kehittämisen perustan muodostavat esimiehen oma esimerkki ja oppimiseen kannustava ilmapiiri. Esimies, joka onnistuu suuntaamaan henkilökuntansa oppimisen tukemaan organisaation tavoitteita, osaa henkilökohtaistaa yhtiön strategian sopimaan jokaisen toimenkuvaan. Oppimisen tukemisessa vaaditaan esimieheltä vahvaa henkilökunnan tuntemusta, tavoitteiden asettamista ja niiden toteutumisen seurantaa. Tutkimus osoitti esimiesten olevan pääsääntöisesti innostuneita työstään ja onnistuvan osaamisen suuntaamisen toimissa hyvin. Esimiehet voisivat kehittää toimintaansa ottamalla oman henkilökuntansa mukaan toiminnan suunnitteluun ja vastuuttamalla heitä myymälän toiminnan ja oman ammattitaitonsa jatkuvaan kehittämiseen.

Scheduling dynamic dataflow graphs with model checking

With the shift towards many-core computer architectures, dataflow programming has been proposed as one potential solution for producing software that scales to a varying number of processor cores. Programming for parallel architectures is considered difficult as the current popular programming languages are inherently sequential and introducing parallelism is typically up to the programmer. Dataflow, however, is inherently parallel, describing an application as a directed graph, where nodes represent calculations and edges represent a data dependency in form of a queue. These queues are the only allowed communication between the nodes, making the dependencies between the nodes explicit and thereby also the parallelism. Once a node have the su cient inputs available, the node can, independently of any other node, perform calculations, consume inputs, and produce outputs. Data ow models have existed for several decades and have become popular for describing signal processing applications as the graph representation is a very natural representation within this eld. Digital lters are typically described with boxes and arrows also in textbooks. Data ow is also becoming more interesting in other domains, and in principle, any application working on an information stream ts the dataflow paradigm. Such applications are, among others, network protocols, cryptography, and multimedia applications. As an example, the MPEG group standardized a dataflow language called RVC-CAL to be use within reconfigurable video coding. Describing a video coder as a data ow network instead of with conventional programming languages, makes the coder more readable as it describes how the video dataflows through the different coding tools. While dataflow provides an intuitive representation for many applications, it also introduces some new problems that need to be solved in order for data ow to be more widely used. The explicit parallelism of a dataflow program is descriptive and enables an improved utilization of available processing units, however, the independent nodes also implies that some kind of scheduling is required. The need for efficient scheduling becomes even more evident when the number of nodes is larger than the number of processing units and several nodes are running concurrently on one processor core. There exist several data ow models of computation, with different trade-offs between expressiveness and analyzability. These vary from rather restricted but statically schedulable, with minimal scheduling overhead, to dynamic where each ring requires a ring rule to evaluated. The model used in this work, namely RVC-CAL, is a very expressive language, and in the general case it requires dynamic scheduling, however, the strong encapsulation of dataflow nodes enables analysis and the scheduling overhead can be reduced by using quasi-static, or piecewise static, scheduling techniques. The scheduling problem is concerned with nding the few scheduling decisions that must be run-time, while most decisions are pre-calculated. The result is then an, as small as possible, set of static schedules that are dynamically scheduled. To identify these dynamic decisions and to find the concrete schedules, this thesis shows how quasi-static scheduling can be represented as a model checking problem. This involves identifying the relevant information to generate a minimal but complete model to be used for model checking. The model must describe everything that may affect scheduling of the application while omitting everything else in order to avoid state space explosion. This kind of simplification is necessary to make the state space analysis feasible. For the model checker to nd the actual schedules, a set of scheduling strategies are de ned which are able to produce quasi-static schedulers for a wide range of applications. The results of this work show that actor composition with quasi-static scheduling can be used to transform data ow programs to t many different computer architecture with different type and number of cores. This in turn, enables dataflow to provide a more platform independent representation as one application can be fitted to a specific processor architecture without changing the actual program representation. Instead, the program representation is in the context of design space exploration optimized by the development tools to fit the target platform. This work focuses on representing the dataflow scheduling problem as a model checking problem and is implemented as part of a compiler infrastructure. The thesis also presents experimental results as evidence of the usefulness of the approach.

Employees’ continuous learning and job satisfaction - effects on productivity

In today’s knowledge intense economy the human capital is a source for competitive advantage for organizations. Continuous learning and sharing the knowledge within the organization are important to enhance and utilize this human capital in order to maximize the productivity. The new generation with different views and expectations of work is coming to work life giving its own characteristics on learning and sharing. Work should offer satisfaction so that the new generation employees would commit to organizations. At the same time organizations have to be able to focus on productivity to survive in the competitive market. The objective of this thesis is to construct a theory based framework of productivity, continuous learning and job satisfaction and further examine this framework and its applications in a global organization operating in process industry. Suggestions for future actions are presented for this case organization. The research is a qualitative case study and the empiric material was gathered by personal interviews concluding 15 employee and one supervisor interview. Results showed that more face to face interaction is needed between employees for learning because much of the knowledge of the process is tacit and so difficult to share in other ways. Offering these sharing possibilities can also impact positively to job satisfaction because they will increase the sense of community among employees which was found to be lacking. New employees demand more feedback to improve their learning and confidence. According to the literature continuous learning and job satisfaction have a relative strong relationship on productivity. The employee’s job description in the case organization has moved towards knowledge work due to continuous automation and expansion of the production process. This emphasizes the importance of continuous learning and means that productivity can be seen also from quality perspective. The normal productivity output in the case organization is stable and by focusing on the quality of work by improving continuous learning and job satisfaction the upsets in production can be handled and prevented more effectively. Continuous learning increases also the free human capital input and utilization of it and this can breed output increasing innovations that can increase productivity in long term. Also job satisfaction can increase productivity output in the end because employees will work more efficiently, not doing only the minimum tasks required. Satisfied employees are also found participating more in learning activities.

Production planning and optimization of a pulp mill: introduction of the optimisation based scheduling software for pulp industry

The objective of this project was to introduce a new software product to pulp industry, a new market for case company. An optimization based scheduling tool has been developed to allow pulp operations to better control their production processes and improve both production efficiency and stability. Both the work here and earlier research indicates that there is a potential for savings around 1-5%. All the supporting data is available today coming from distributed control systems, data historians and other existing sources. The pulp mill model together with the scheduler, allows what-if analyses of the impacts and timely feasibility of various external actions such as planned maintenance of any particular mill operation. The visibility gained from the model proves also to be a real benefit. The aim is to satisfy demand and gain extra profit, while achieving the required customer service level. Research effort has been put both in understanding the minimum features needed to satisfy the scheduling requirements in the industry and the overall existence of the market. A qualitative study was constructed to both identify competitive situation and the requirements vs. gaps on the market. It becomes clear that there is no such system on the marketplace today and also that there is room to improve target market overall process efficiency through such planning tool. This thesis also provides better overall understanding of the different processes in this particular industry for the case company.

Laserhitsattavan tuotteen suunnittelu

Tässä työssä tarkastellaan laserhitsattavan tuotteen suunnittelua ja sen tuotekehitykseen liittyviä tekijöitä. Tuotteen suunnittelua käsitellään valmistuksellisesta näkökulmasta, eli siitä, kuinka tuotteen suunnittelussa voidaan ottaa huomioon tuotteen valmistus- ja kokoonpanoystävällisyys. Laserhitsattavan tuotteen suunnittelua käsitellään myös tuotteen ominaisuuksien kannalta, eli kuinka lopullisesta tuotteesta saadaan mahdollisimman laadukas ja kilpailukykyinen. Suomen kaarihitsausosaaminen on kansainvälisesti korkealuokkaista, mutta laserhitsaus eroaa perinteisistä kaarihitsausprosesseista paljon. Kun laserilla hitsattavaa tuotetta suunnitellaan, ovat menetelmäkohtaiset suunnittelusäännöt erilaiset kuin kaarihitsauksessa. Laserhitsaus vaatii teknisesti pajalta enemmän, mutta se myös avaa uusia ovia tuotesuunnittelulle ja mahdollistaa tuotteita, jotka olisivat perinteisillä menetelmillä hankalia tai mahdottomia valmistaa. Oikein käyttöönotettuna laserhitsauksella voidaan päästä matalampiin valmistuskustannuksiin. Kustannustehokkaaseen tuotantoon päästäkseen täytyy kuitenkin ymmärtää tuotteen kustannusrakenne. Työn lopussa tarkastellaan ja vertaillaan perinteisen ja laserhitsatun tuotteen kustannuksia ja kustannusrakennetta.

A multimethod examination of contributors to successful on-the-job learning for vocational students

Rapid changes in working life and competence requirements of different professions have increased interest in workplace learning. It is considered an effective way to learn and update professional skills by performing daily tasks in an authentic environment. Especially, ensuring a supply of skilled future workers is a crucial issue for firms facing tight competition and a shortage of competent employees due to the retirement of current professionals. In order to develop and make the most of workplace learning, it is important to focus on workplace learning environments and the individual characteristics of those participating in workplace learning. The literature has suggested various factors that influence adults' and professionals’ workplace learning of profession-related skills, but lacks empirical studies on contextual and individual-related factors that positively affect students' workplace learning. Workers with vocational education form a large group in modern firms. Therefore, elements of vocational students’ successful workplace learning during their studies, before starting their career paths, need to be examined. To fill this gap in the literature, this dissertation examines contributors to vocational students’ workplace learning in Finland, where students’ workplace learning is included in the vocational education and training system. The study is divided into two parts: the introduction, comprised of the overview of the relevant literature and the conclusion of the entire study, and five separate articles. Three of the articles utilize quantitative methods and two use qualitative methods to examine factors that contribute to vocational students’ workplace learning. The results show that, from the students’ perspective, attitudinal, motivational, and organizationrelated factors enhance the student’s development of professionalism during the on-the-job learning period. Specifically, the organization-related factors such as innovative climate, guidance, and interactions with seniors have a strong positive impact on the students’ perceived development of professional skills because, for example, the seniors’ guidance and provision of new viewpoints for the tasks helps the vocational students to gain autonomy at work performance. A multilevel analysis shows that of those factors enhancing workplace learning from the student perspective, innovative climate, knowledge transfer accuracy, and the students’ performance orientation were significantly related to the workplace instructors’ assessment regarding the students’ professional performance. Furthermore, support from senior colleagues and the students’ self-efficacy were both significantly associated with the formal grades measuring how well the students managed to learn necessary professional skills. In addition, the results suggest that the students’ on-the-job learning can be divided into three main phases, of which two require efforts from both the student and the on-the-job learning organization. The first phase includes the student’s application of basic professional skills, demonstration of potential in performing daily tasks, and orientation provided by the organization at the beginning of the on-the-job learning period. In the second phase, the student actively develops profession-related skills by performing daily tasks, thus learning a fluent working style while observing the seniors’ performance. The organization offers relevant tasks and follows the student’s development. The third level indicates a student who has reached the professional level described as a full occupation. The results suggest that constructing the vocational students’ successful on-the-job learning period requires feedback from seniors, opportunities to learn to manage entire work processes, self-efficacy on the part of the students, proactive behavior, and initiative in learning. The study contributes to research on workplace learning in three ways: firstly, it identifies the key individual- and organization-based factors that influence the vocational students’ successful on-the-job learning from their perspective and examines mutual relationships between these factors. Second, the study provides knowledge of how the factors related to the students’ view of successful workplace learning are associated with the workplace instructors’ perspective and the formal grades. Third, the present study finds elements needed to construct a successful on-the-job learning for the students.

De auro e septentrione Job. XXXVII: v. 22

Invokaatio: I.N.J.