Mahdjoub S E Moussavi

M Grunder

Keywords: Human resource planning, Job rotation scheduling, Heuristic and matheuristic optimization

Titre : Workforce scheduling and job rotation by considering ergonomic factors: Application to production and home healthcare systems Mots-clés : problème de planification du personnel, Rotation des tâches, Approaches d'optimisation

Résumé :

Cette thèse porte sur la planification du personnel en accordant une attention particulière à l'aspect humain et aux facteurs ergonomiques dans le domaine de la production. Un certain nombre de modèles mathématiques sont présentés pour formuler les problèmes d'ordonnancement et de planification du personnel étudiée. Dans les modèles de planification, la productivité du système de fabrication et le bien-être des travailleurs sont ciblés. De cette manière, une approche d'affectation des travailleurs est présentée pour réduire le temps de production et une approche d'ordonnancement des rotations des tâches est présentée pour équilibrer les charges de travail sur les opérateurs. A cet effet, une analyse ergonomique est effectuée sur les postes de travail du système de production étudié. Cette analyse aboutit à l'évaluation des postes du travail par rapport du feu de circulation, c'est-à-dire que les postes sont classés dans les niveaux de charge faible, moyen et élevé qui sont présentés respectivement par les couleurs verte, jaune et rouge. Une approche mathématique est développée pour convertir ces sorties en valeurs numériques, car les paramètres quantitatifs sont plus applicables pour l'optimisation de la planification. Une programmation multi-objectifs est proposée pour optimiser deux objectifs mentionnés du problème d'ordonnancement de tounée du personnel étudiée. Les méthodes d'agrégation linéaire et de contrainte epsilon sont appliquées pour résoudre ce modèle d'optimisation. En outre, cette thèse présente une nouvelle variante du problème d'affectation appelé problème d'affectation généralisée de séquençage qui est défini pour la planification du personnel dans un système combiné constitué des postes de travail en série et en parallèle. Il est prouvé que ce problème d'optimisation combinatoire est NP-hard et les méthodes exactes ne sont pas capables de résoudre les instances à grande échelle. Ainsi, trois méthodes approximatives composées de deux approches matheusistiques et une heuristiques hybrides sont développées pour résoudre ce problème. Les méthodes matheuristiques sont basées sur la décomposition de la formulation pour décomposer et simplifier le modèle principal en deux ou plusieurs modèles plus petits. La troisième méthode est une avide heuristique combinée à une recherche locale. En outre, dans la dernière étape de cette thèse, la planification des ressources humaines pour un système de soins à domicile est formulée mathématiquement. Selon la structure du système, une intégration des problèmes d'affectation et de tournées de véhicules est présentée. Enfin, une approche matheuristique en trois étapes est proposée pour résoudre ce problème d'optimisation combinatoire.

This thesis concerns the human resource planning by paying a special attention to the human aspect and ergonomic factors in the manufacturing domain. A number of mathematical models are presented to formulate the studied workforce scheduling and planning problems. In the planning models, the productivity of the manufacturing system and the well-being of the workers are targeted. In this way, a worker assignment approach is presented to reduce the production time and a job rotation scheduling approach is presented to balance the workloads on the operators. For this purpose, an ergonomic analysis is carried out on the jobs of the studied production system. This analysis results in the traffic light evaluation for the jobs, i.e., the jobs are categorized into the low, medium and high workload levels which are presented respectively by the green, yellow and red colors. A mathematical approach is developed to convert these outputs to the numerical values, because the quantitative parameters are more applicable for the optimization of the planning. A multi-objective programming is proposed to optimize two mentioned objectives of the studied workforce scheduling problem. Both linear aggregation and epsilon-constraint methods are applied to solve this optimization model. Furthermore, this thesis presents a novel variant of the assignment problem called sequencing generalized assignment problem which is defined for workforce scheduling in a combined system consisting of the jobs in series and in parallel. It is proved that this combinatorial optimization problem is NP-hard and the exact methods are not able to solve the large-scale instances. Hence, three approximate methods consisting of two matheuristic and a hybrid heuristic approaches are developed to solve that. The matheuristic methods are based on the decomposition of the formulation to break down and simplify the main model into two or more smaller models. The third method is a greedy heuristic combined with a local search. The efficiency of three mentioned methods is evaluated by various instances of different sizes. Moreover, in the last step of this thesis, the human resource planning for a home healthcare system is formulated mathematically. According to the structure of the system, an integration of the worker assignment and vehicle routing problems is presented. Finally, a threesteps matheuristic approach is proposed to solve this combinatorial optimization problem.

GENERAL INTRODUCTION

The human aspect is an important factor in the analysis of the productivity and efficiency of a production or service system. In the manufacturing, the efficiency of the workers and their capacities cause the uncertain executing time for the production tasks. In the real cases, the efficiency of the workers varies from a task to another, so that the best worker for a task is not necessarily the best for another task. Hence, assigning the best worker to each task can significantly improve the productivity of the system. Thus, the human resource planning in a production system could be considered as a specific version of the Assignment Problem (AP). Moreover, the job rotation scheduling also plays an important role in the workforce planning domain as well, particularly where the ergonomic issues are considered as the objectives or constraints in the planning. Actually, reducing musculoskeletal disorders (MSD), risk factors and monotony of the work are the main reasons that persuade a manufacturing industry to apply job rotation in the manpower planning. Many various objectives can be targeted in the manpower planning of a system. In the production domain, improving the productivity, reducing the production cycle time or manpower costs... are the economical objectives and workload balancing, reducing the ergonomic risks, MSDs, and occupational disease are the ergonomic objectives of the workforce planning. In a service system, for instance a home delivery system, the objective of the planning can be minimizing the distance travelled by the staff members, reducing the travel costs, ... In the last decades, the Operational Research's (OR) approaches have been employed to manage and optimize the human resource planning in diverse domains. The mixedinteger programming (MIP), linear programming (LP), mixed-integer linear programming (MILP), ... are the optimization approaches which have been widely applied to formulate mathematically a human resource planning problem. In this way, various operational research's problems were developed. For instance Assignment Problem (AP), Travel Salesman Problem (TSP), and Vehicle Routing Problem (VRP) are some well-known problems for the operations and personnel management. In the personnel management domain, the assignment problem is frequently used as the basis to formulate the problem mathematically. The classical assignment problem concerns a number of agents and a number of tasks. Any agent can be assigned to perform any task with an operating time that may vary depending on the agent-task assignment. A simple example of the classical assignment problem is shown in figure 1.1. This thesis is composed of three parts. The first part concerns a human resource planning in a continuous manufacturing system in which the ergonomic considerations play the important roles. At the first step of this part, the ergonomic criteria are considered to FIGURE 1.1 -Classical Assignment Problem develop a worker assignment by the aim of improving the productivity. It is proved that the ergonomic adequation level between worker and job has an impact on the efficiency of the worker. Thus, the operating time of the workers vary according to their ergonomic adequation level with the job. In this way, an integer linear mathematical model based on the assignment problem is proposed to reduce the daily production cycle time by an ergonomic workforce scheduling. The worker assignment in this part of research is not directly based on the ergonomic criteria but that is based on the workers' operating times where the operating times are depended on the ergonomic adequation between worker and job.

At the second step of the first part, the ergonomic factors are directly considered in the workforce planning. In the same production system, various ergonomic criteria are taken into account to calculate the workloads of each job. This analysis shows that the workload level largely varies from a job to another. Hence, a job rotation approach is proposed by the aim of balancing the daily workloads among the workers. This optimization problem is also formulated mathematically by using mixed-integer programming. Finally, at the third and last step of this part, both studied objectives (productivity improvement and workload balancing) are integrated in the same problem. A multi-objective optimization approach is proposed to implement an ergonomic worker assignment and job rotation schedule in the studied production line. This approach improves the productivity and balances the operators' workloads simultaneously.

Three presented models in the first part do not follow a well-known problem formulation in the OR domain. According to the structure of the studied system, in the second part of this thesis, the Generalized Assignment Problem (GAP) is used as the basis of the formulation for the manpower planning models. The GAP is an enlarged version of the classical assignment problem in which the assignment of several tasks to an agent is possible. The only restriction that can limit the assignment of the tasks to the agents is the capacity of the agent. In this part, the manpower planning in the studied assembly line is modelled as a GAP. The considered assembly line consists of a number of workstations in series where each workstation contains several jobs in parallel. The presented optimization model in this part seeks to assign the best operator to the jobs in order to minimize the processing time in each workstation and in the whole of the system. The generalized assignment formulation is adapted to this case. Moreover, the objective is to perform an efficient human resource planning for a specified horizon consisting of several periods. Hence, we present an extension of the generalized assignment problem, consisting of a set of GAPs (one for each planning period) in which each GAP depends on previous ones. A mixed integer mathematical model is presented for this sequencing assignment problem.

It is proved that the problem is NP-hard and solving the medium and large size instances is not possible by the exact algorithms. Hence, three approximate solution methods are presented for this novel optimization problem : Two matheuristic approaches based on the disaggregated formulation of GAP and also a heuristic algorithm. The first matheuristic approach solves the problem through two sub-problems as the transportation formulation and assignment formulation. The second matheuristic approach solves the problem by decomposition of the problem into several classical GAPs. The heuristic algorithm is a greedy heuristic combined with a local search.

In some cases, the modelization of the human resource planning problem by using only assignment problem formulation is not possible. For instance, the manpower planning in a home delivery service deals with two different OR aspects. The first is the Assignment Problem (AP) and the second is a variant of the Vehicle Routing Problem (VRP). In the last years, the home health care planning problem has been widely studied as a novel OR problem in the human resource planning domain. The third and last part of this thesis concerns the workforce planning in a home health care system, which is a special type of the home delivery service. Both assignment and vehicle routing formulations are used to model this combinatorial optimization problem. To model a home healthcare planning problem by classical VRP and AP formulation, the dimensions of the problem are : 1. The staffs, 2. The patients, 3. The routes (sequence of the patients for each staff).

In this thesis, we present an extension of the home healthcare planning problem by adding an extra dimension of time so that the staffs are not only assigned to the patients, but they are also assigned to the daily periods. The horizon of the planning problem contains multiple days in which the patients' needed services vary from one day to another. Hence, the problem concerns a sequence of plannings (one planning for each day) for the staff members. This variant of the home healthcare planning problem is modelled mathematically by employing the sequencing generalized assignment formulation which is presented in part two. Considering that, the studied combinatorial optimization problem is NP-complete, a matheuristic approach based on the decomposition of the formulation is proposed in this research to simplify the mathematical model and reduce the computational time needed to solve the problem. Actually, in this part of thesis, two mathematical programming approaches are presented to integrate the generalized assignment and vehicle routing problems.

STATE OF THE ART 2.1/ INTRODUCTION

Human and machine factors are two considerable agents which have the important impact on the productivity in the manufacturing environment. Because of being various difficulties in modelling the human issues, this aspect has not been greatly considered in the previous researches. Nevertheless, it is a substantial factor in the production not only for its influence on the productivity but also to control the ergonomic risks which play the important role in such systems. Nowadays, work-related musculoskeletal disorders (WMSDs) and ergonomic risks have received a considerable amount of attention in the manufacturing.

In various researches, job rotation is defined as a solution to balance workloads and reduce the ergonomic risks among operators. Moreover, considering the ergonomic aspect in the job assignment procedure may decrease WSMDs and its associated risks in manufacturing lines. The job assignment and job rotation, as the two main branches of the workforce scheduling problem (WSP), have been widely studied in the literature. This thesis concerns the human resource planning for two different systems : 1. A manufacturing system (figure 2.1) ; 2. A home healthcare system. For the first system, the objective is to improve the productivity, while the ergonomic factors have been considered for the worker assignment. Then, a job rotation approach has been proposed to balance the workloads to which the workers are exposed. In the next step, a multi-objective approach has been proposed to combine two mentioned objectives by aiming to improve the productivity and reduce the ergonomic risks simultaneously. In the next step, the human resource planning for this manufacturing system is formulated based on the Generalized Assignment Problem (GAP).

The human resource planning in a home healthcare system is a combinatorial optimization problem, because the staffs are not only assigned to the services (jobs) but they must also move from a patient to another. Therefore, this problem deals with both assignment and vehicle routing problems. A state of the art is presented for all aforementioned aspects of this thesis as follows. In the two last decades, diverse objectives have been purposed for the workforce scheduling problems. For instance, [START_REF] Alfares | Optimum workforce scheduling under the (14, 21) days-off timetable[END_REF] proposed an optimal job allocation to the employees such that minimize the number workers by regarding the successive work-days and also the successive off-days. Total labor cost is another objective which is targeted in a paper published by [START_REF] Elshafei | A dynamic programming algorithm for daysoff scheduling with sequence dependent labor costs[END_REF]. [START_REF] Seçkiner | Ant colony optimization for the job rotation scheduling problem[END_REF] and [START_REF] Michalos | Dynamic job rotation for workload balancing in human based assembly systems[END_REF] published papers on workforce scheduling domain by modelling the job rotation. Their works are aimed at, respectively, minimizing the workload of jobs and balancing workload in the automotive assembly line.

Personal features of the worker are another considerable aspect for assessment of human factor in the manufacturing. In this way, [START_REF] Costa | Job rotation in assembly lines employing disabled workers[END_REF] proposed a metric to evaluate the efficiency of job rotation in the case of disabling workers. Their objective was to minimize the number of different jobs which are performed by each worker. [START_REF] Othman | Workforce scheduling : A new model incorporating human factors[END_REF] developed a multi-objective mixed integer model on the workforce scheduling by considering human aspects and worker differences such as skills, fatigue, and personalities. The objective of their model consists of productivity and economic aspects. After that, [START_REF] Moreira | Hybrid heuristics for planning job rotation schedules in assembly lines with heterogeneous workers[END_REF] published another paper on the job rotation problem with paying specific attention to the personality, body and mental characterizations of workers. They proposed a hybrid algorithm for selecting the appropriate schedules from a pool of solutions at each period. Smoothing the workload among the heterogeneous workers was their objective.

In the above-mentioned studies, the researchers have not directly addressed the ergonomic aspect in their job rotation and assignment problems whereas in two last decades divers papers have been published on the workforce scheduling with significant ergonomic considerations as the main issues. [START_REF] Rattanamanee | Multi-workday ergonomic workforce scheduling with days off[END_REF] proposed an ergonomic job assignment for a production system. Ergonomic aspect was depicted as daily hazard caused by working in the different workstations. The objective was to minimize the number of employees for the planning period such that the daily hazard does not exceed an allowable limit for each worker. Ergonomic risks were targeted in another paper published by [START_REF] Otto | Reducing ergonomic risks by job rotation scheduling[END_REF], in which a model was presented for balancing the ergonomic risk among workers using job rotation scheduling. A comprehensive evaluation of workstation was performed with the aim of risk assessment in different tasks of an automotive production line. These two studies did not consider the difference between the personal characterization of workers.

Very few researches have considered the ergonomic aspect of jobs together with personal features and capacities of each operator, in the workforce scheduling. For example, [START_REF] Azizi | Modeling job rotation in manufacturing systems : The study of employee's boredom and skill variations[END_REF] presented a dynamic model for job rotation. In their model, job rotation has a negative effect on the efficiency of workers because of the skill forgetting ; And has a positive effect thanks to the raising the motivation level. Their principle objective was to determine the optimal interval for rotation the tasks by considering the mental personal factors of workers. In another research developed by [START_REF] Huang | Ergonomic job rotation strategy based on an automated rgb-d anthropometric measuring system[END_REF], anthropometry, which is a physical factor in the ergonomic domain, is considered in their job rotation approach. Reducing the average risk and decreasing the number of workers who experience the high level of risk, are their objectives. They performed a risk assessment according to the difference between the anthropometry of the operator and what needed by the job. Furthermore, [START_REF] Van Den Bergh | Personnel scheduling : A literature review[END_REF] reviewed comprehensively the literature on workforce scheduling and classified them according to their objectives, constraints, considerations, assumptions, and applications. They identified different perspectives such as demand forecasting, hiring and firing, machine scheduling. Next section presents a state of the art on the different ergonomic risks and criteria which can be considered for human resource planning in the manufacturing domain.

2.2.2/ ERGONOMICS AND RISK FACTORS IN THE MANUFACTURING

Work-related musculoskeletal disorders (WR-MSDs) develop due to exposure to risk factors and represent one third of all diagnosed work-related diseases in the manufacturing domain in many countries [START_REF] Chiasson | Comparing the results of eight methods used to evaluate risk factors associated with musculoskeletal disorders[END_REF]). They have significant financial and social consequences which result in more than 40% of occupational costs [START_REF] Speklé | The cost-effectiveness of the rsi quickscan intervention programme for computer workers : Results of an economic evaluation alongside a randomised controlled trial[END_REF]). Many industries in France have experienced increases in the number of workers' compensation claims in recent decades due to WR-MSDs risk factors [START_REF] Rivière | Underreporting of musculoskeletal disorders in 10 regions in france in 2009[END_REF] ; [START_REF] Roquelaure | Epidemiologic surveillance of upper-extremity musculoskeletal disorders in the working population[END_REF]). Repetitive tasks, work posture, lifting and material handling, energy consumption, and tooling are common WR-MSDs risk factors in various industries [START_REF] Falck | Assembly failures and action cost in relation to complexity level and assembly ergonomics in manual assembly (part 2)[END_REF]). There are other factors such as the frequency of actions, duration of repetitive tasks over a day and lack of recovery time that intensify the impact of these risk factors [START_REF] Berlin | Corporate-internal vs. national standard-a comparison study of two ergonomics evaluation procedures 131 used in automotive manufacturing[END_REF]). An ergonomic approach including the assessment of risk factors, engineering and administrative strategies need to improve the workplace situation in order to provide the positive effects on system and human performance [START_REF] Côté | Quebec research on work-related musculoskeletal disorders : deeper understanding for better prevention[END_REF][START_REF] Fuller | Posture-movement changes following repetitive motion-induced shoulder muscle fatigue[END_REF] ; [START_REF] Widanarko | Interaction between physical and psychosocial risk factors on the presence of neck/shoulder symptoms and its consequences[END_REF]).

Job rotation as an organizational approach is used by manufacturing industries aimed at mitigating exposure to high physical workload and monotony. Figure 2.2 shows a simple example of the shift-based job rotation approach. Researchers often recommend to reduce exposure to risk factors using job rotation [START_REF] Fallentin | Evaluation of physical workload standards/guidelines from a nordic perspective[END_REF] ; [START_REF] Wells | Time-a key issue for musculoskeletal health and manufacturing[END_REF]). This rotation allows transmission of workload to other muscles and increases utilization of different body region. For instance, [START_REF] Mathiassen | Diversity and variation in biomechanical exposure : what is it, and why would we like to know ?[END_REF] suggested that more physical variation may be an effective act against MSDs for the repetitive jobs. Furthermore, job rotation strategy has been frequently applied by engineers following the implementation of lean management, because of the need for more workers with autonomy [START_REF] Padula | Job rotation designed to prevent musculoskeletal disorders and control risk in manufacturing industries : A systematic review[END_REF]). However, efficiency of a job rotation strategy depends on identifying workloads, evaluating exposure level, and proper planning and schedule of job rotation [START_REF] Otto | Reducing ergonomic risks by job rotation scheduling[END_REF]).

FIGURE 2.2 -A shift-based job rotation approach

To develop a job rotation strategy, previous studies have considered different types of ergonomic parameters to characterize physical workload. Various methods such as direct measurement tools [START_REF] Jonsson | Electromyographic studies of job rotation[END_REF] ; [START_REF] Balogh | Increasing the degree of automation in a production system : consequences for the physical workload[END_REF]), NIOSH lifting equation, Rapid Upper Limb Assessment, Occupational Repetitive Actions (Asensio-Cuesta et al. ( 2012)), Rapid Entire Body Assessment [START_REF] Triggs | Job rotation[END_REF] ; [START_REF] Yoon | A model for developing job rotation schedules that eliminate sequential high workloads and minimize between-worker variability in cumulative daily workloads : Application to automotive assembly lines[END_REF]), Occupational Repetitive Actions [START_REF] Otto | Incorporating ergonomic risks into assembly line balancing[END_REF]) and checklists have been frequently used to assess physical workloads. However, few studies have integrated various biomechanical parameters such as repetition, postures, force, material handlings and energy consumption into a mathematical model for job rotation. [START_REF] Frazer | The effects of job rotation on the risk of reporting low back pain[END_REF] suggested integrating several risk factors such as force and repetition to effectively reduce physical workload. Their paper is an experimental study on the effect of job rotation on risk predictions of reporting low back pain, using the two approaches Low Back Pain Reporting (LBPR) and Time Weighted Average (TWA). In another research, [START_REF] Leider | When is job rotation perceived useful and easy to use to prevent work-related musculoskeletal complaints ?[END_REF] showed that knowledge about exposure to physical workload at organizational and individual levels could facilitate the implementation of job rotation as a useful or easy to use ergonomic intervention.

Furthermore, the impact of the job rotation approach on the biomechanical factors and well-being of workers are analysed by [START_REF] Aptel | Proposal of parameters to implement a workstation rotation system to protect against msds[END_REF]. They concluded that a job rotation schedule must consider all the dimensions of the work particularly biomechanical parameters. [START_REF] Yoon | A model for developing job rotation schedules that eliminate sequential high workloads and minimize between-worker variability in cumulative daily workloads : Application to automotive assembly lines[END_REF] proposed a job rotation schedule in a production assembly line that successfully reduce cumulative workloads on the same body region. However, physical workloads were identified and assessed by REBA tool which focus on whole body postural analysis. Furthermore, learning aspect and its cost/time were ignored in this mathematical model. [START_REF] De Oliveira Sato | Evaluation of musculoskeletal health outcomes in the context of job rotation and multifunctional jobs[END_REF] found a great variability in the pattern of exposure to physical workloads when workers rotate between workstations. Thus, appropriate indicators must consider to evaluate physical workloads and to be sensitive to the effects of work variability. In order that practitioners could apply the theoretical achievement in the real industrial settings, [START_REF] Otto | Reducing ergonomic risks by job rotation scheduling[END_REF] confirmed that a comprehensive analysis of physical workloads closer and applicable to the real settings is required to define the parameters and the objective functions of the mathematical model for job ro-tation schedules. In fact, their paper illustrates a binary linear program for the ergonomic job rotation scheduling problem (EJRSP) which uses period-specific ergonomic points (EP) from the EAWS for the definition of the risk exposures and of the objective function. Then, a smoothing heuristic solution method is proposed. In this way, [START_REF] Moussavi | Reducing production cycle time by ergonomic workforce scheduling[END_REF] proposed a job rotation model to perform a workforce scheduling in a real setting assembly line. They analyzed some ergonomic factors on the operators and on the jobs to assign the most appropriate worker to each job.

Application of job rotation schedules developed in various studies to the real settings has been less considered in the literature. Learning-forgetting effect and its related time/cost have been often neglected in the developed job rotation model such that these theoretical model could not be applied to the real settings [START_REF] Azizi | Modeling job rotation in manufacturing systems : The study of employee's boredom and skill variations[END_REF]). All aforementioned researches are the mono-objective job rotation problems. They considered whether productivity or ergonomic factors as the objective function. In the next section a state of the art is presented on the multi-objective job rotation scheduling problems.

2.2.3/ MULTI-OBJECTIVE APPROACH IN THE WORKFORCE SCHEDULING

As mentioned before, various objectives have been targeted in the human resource planning domain. In the classical assignment problem the economical objectives are often considered, but in the classical job rotation, the ergonomic factors are usually taken into account. Moreover, there are the researches that consider the productivity in the job rotation models. According to the divers origins and domains of the objectives of job rotation, a main objective is mostly purposed and the other aspects are often ignored or are analyzed very slightly. A few studies have considered a multi-criteria optimization in the job rotation, worker assignment and human factors in the production domain. In this way, [START_REF] Costa | Job rotation in assembly lines employing disabled workers[END_REF] studied a job rotation, worker assignment problem in an assembly line. They only considered the disabled workers and training aspect in their job rotation model. The optimization of the human factors in the production is considered in the research by [START_REF] Grosse | Incorporating human factors into decision support models for production and logistics : current state of research[END_REF]. They studied the state of art of the incorporating human factors in the production and logistics. The work-related musculoskeletal disorders were considered in the job rotation model presented by [START_REF] Botti | Design of job rotation schedules managing the exposure to age-related risk factors[END_REF]. Their objective was to reduce the ergonomic risks and assigning the skilled workers to each jobs . They proposed a bi-objective mathematical model for their job rotation strategy. In other multicriteria researches, [START_REF] Rossi | A multicriteria ergonomic and performance methodology for evaluating alternatives in "manuable" material handling[END_REF] proposed an AHP approach to evaluate various scenarios containning humain factor and productivity considerations. Two multi-criteria optimizations, one in job rotation and another in worker assignment proposed by respectively [START_REF] Diego-Mas | A multi-criteria genetic algorithm for the generation of job rotation schedules[END_REF] and [START_REF] Hussin | Hybrid simulated annealing for the bi-objective quadratic assignment problem[END_REF].

Line Balancing and it's related problems are the well-known optimization problems in the production systems. The human factors, ergonomic risks, productivity and multi-criteria optimization were largey considered in this domain in the last years. In this way, Battini et al. (2016a) presented a novel extension of the line balancing problem and they proposed a mixed-integer model by considering the ergonomic factors. They have shown that how their proposed optimization approach reduce the inventories and the fatigue of workers. [START_REF] Moussavi | Productivity improvement through a sequencing generalised assignment in an assembly line system[END_REF] and [START_REF] Moussavi | A hybrid heuristic algorithm for the sequencing generalized assignment problem in an assembly line[END_REF] proposed a new extension of assignment problem and job rotation for worker assignment in the production. The ergonomic aspect was considered in the line balancing in the research by [START_REF] Sgarbossa | Including ergonomics aspects into mixed-model assembly line balancing problem[END_REF] where a multi-objective programming approach was presented to incorporate the ergonomics criteria and the assembly line balancing problem. Apart from the ergonomic criteria, the energy expenditure is also studied in their work. In this way, [START_REF] Battini | Ergonomics in assembly line balancing based on energy expenditure : a multi-objective model[END_REF] in another research proposed a multi-objective model containing four different objectives to evaluate the impact of the ergonomic criteria on the line balancing performance. They used the energy expenditure to obtain the level of the ergonomics.

Another domain of application for the optimization by ergonomic criteria in the production is cell formation problem. [START_REF] Niakan | A multi-objective mathematical model considering economic and social criteria in dynamic cell formation[END_REF] proposed a multi-objective mixed integer model to the cellular manufacturing system that considers social factors together with the economic criteria and they proposed a hybrid genetic algorithm to solve their model. The problem studied by [START_REF] Akyol | Ergoalwabp : a multiple-rule based constructive randomized search algorithm for solving assembly line worker assignment and balancing problem under ergonomic risk factors[END_REF] is a integration of the worker assignment and line balancing problems. They analyzed the ergonomic risks in their problem as the main consideration. A heuristic solving approach was proposed for their problem.

Actually, this thesis aims at obtaining the optimal assignment of the appropriate operators to the workstations. Considering the structure of the studied assembly line that consists of the workstations which are in series (flowshop system) and each workstation is composed of several jobs. In a workstation, as there are no precedence relationships between jobs, they can be processed in parallel. Consequently, several workers are assigned to the same workstation. Therefore, the studied problem can be regarded as a special type of the generalized assignment problem (GAP) which is a combinatorial optimization problem. The presented worker assignment researches in the previous sections are not based on a particular well-known problem formulation. In the next section, a state of the art on the workers assignment formulation based on the GAP is presented.

2.3/ WORKER ASSIGNMENT BASED ON THE GAP

For the first time, the term generalized assignment problem is introduced by [START_REF] Ross | A branch and bound algorithm for the generalized assignment problem[END_REF] as multiple assignments of tasks to agents which are limited by some resource available to the agents. Figure 2.3 shows a simple example of the GAP containing three workers and 6 jobs with a capacity of two jobs for each worker. For the GAP, [START_REF] Ross | A branch and bound algorithm for the generalized assignment problem[END_REF] Proposed a branch and bound algorithm and compared that with two other algorithms named IPNETG presented by [START_REF] Klingman | Computational testing on an integer generalized network code[END_REF] and also a zero-one algorithm presented by De [START_REF] De Maio | An all zero-one algorithm for a certain class of transportation problems[END_REF]. They demonstrated the advantages of their algorithm in the computational time and precision of the solution by examining the different size of the problem. Another exact method which has been employed to solve the classical GAP is the Lagrangian relaxation approach in the researches by [START_REF] Jörnsten | A new lagrangian relaxation approach to the generalized assignment problem[END_REF] and [START_REF] Fisher | A multiplier adjustment method for the generalized assignment problem[END_REF] . After that [START_REF] Cattrysse | A survey of algorithms for the generalized assignment problem[END_REF] presented a survey on the different relaxation algorithms which had been proposed for the generalized assignment problem. Various extension of the GAP such as bottleneck generalized assignment problem (BGAP) and non-linear capacity constraints (NLGAP) were presented in their research. In this way, [START_REF] Savelsbergh | A branch-and-price algorithm for the generalized assignment problem[END_REF] proposed an exact algorithm by using the column generation and branch and bound approaches for this kind of problems.

Apart from the exact algorithms, divers approximation algorithms have been presented for the GAP. In the literature, there exist the heuristics, metaheuristics and hyper-heuristics approaches. [START_REF] Shmoys | An approximation algorithm for the generalized assignment problem[END_REF] adapted a generalized assignment problem to the scheduling of the parallel machines and proposed a polynomial-time algorithm, as an approximation method, to solve this problem. Tabu search has been employed by many researchers for the various extensions of the GAP. [START_REF] Laguna | Tabu search for the multilevel generalized assignment problem[END_REF] presented the multilevel generalized assignment problem (MGAP), as an extension of the GAP, in which the efficiency of the agents depend on the number of tasks assigned to those. They proposed a tabu search algorithm with the ejection chain for the neighborhoods definition. Another tabu search heuristic for the GAP is proposed by [START_REF] Dıaz | A tabu search heuristic for the generalized assignment problem[END_REF] in which a dynamic adjustment for the feasibility violation penalty is defined by using a medium-term memory. A hybrid of the heuristic strategy of tabu search with the exact branch and bound approach is proposed by [START_REF] Woodcock | A hybrid tabu search/branch & bound approach to solving the generalized assignment problem[END_REF] to solving the generalized assignment problem . They validated their method by benchmark instances and comparison with other heuristic approaches in the literature. Among the metaheuristic approaches, the genetic algorithm has been also employed for the generalized assignment problem. For instance, [START_REF] Chu | A genetic algorithm for the generalised assignment problem[END_REF] and [START_REF] Wilson | A genetic algorithm for the generalised assignment problem[END_REF] illustrated the advantages of this method for such problems in comparison with earlier works.

In fact, [START_REF] Chu | A genetic algorithm for the generalised assignment problem[END_REF] proved that the generalized assignment problem is an NPcomplete combinatorial optimization and the existing exact methods are practical only for certain instances where there are no additional constraints. Therefore, they proposed a genetic algorithm which is able to solve the GAPs with more constraints. They also compared their adaptive genetic algorithm with various existing approaches, for instance, tabu search and simulated annealing which were adapted for the GAP by [START_REF] Osman | Heuristics for the generalised assignment problem : simulated annealing and tabu search approaches[END_REF]. They presented the results of the genetic algorithm for different instances and demonstrated that the results are extremely near to the optimal solution which is obtained by CPLEX mixed integer solver.

Thereafter, various heuristic and meta-heuristic approaches have been proposed for the generalized assignment problem. For instance, [START_REF] Osorio | Logic cuts for multilevel generalized assignment problems[END_REF] and [START_REF] Dıaz | A tabu search heuristic for the generalized assignment problem[END_REF] considered the generalized assignment problems as the subproblems in their studies and they added more details and assumptions to the classical GAP. They prove that these type of problems are much more complicated than classical GAP to solve and proposed the tabu search and logic cuts in a branch and bound algorithm for solving such problems. In this way, [START_REF] Tasgetiren | Differential evolution algorithms for the generalized assignment problem[END_REF] presented a continuous optimization algorithm based on differential evolution for the GAP and they hybridized their algorithm by employing variable neighborhood search to improve the quality of the solutions. [START_REF] Moccia | A column generation heuristic for a dynamic generalized assignment problem[END_REF] proposed a column generation algorithm to compute a lower bound by linear relaxation and find a feasible integer solution for the dynamic GAP. [START_REF] Posta | An exact method with variable fixing for solving the generalized assignment problem[END_REF] presented an exact algorithm based on the decomposition of the GAP formulation by fixing certain variables.

The uncertainty considerations were also studied in the more recent researches as an extension of the GAP. In this domain, an approximation algorithm based on the combinatorial local search has been presented for the GAP by [START_REF] Cohen | An efficient approximation for the generalized assignment problem[END_REF] . [START_REF] Kiraz | Hyper-heuristic approaches for the dynamic generalized assignment problem[END_REF] proposed another combinatorial algorithm for an extension of the GAP. They presented a dynamic GAP and proposed an integration of the hyper-heuristic with the memory-search algorithm to solve such problems. [START_REF] Subtil | Using an enhanced integer nsga-ii for solving the multiobjective generalized assignment problem[END_REF] also proposed an adapted version of the genetic algorithm by considering non-dominated sorting for another extension of the GAP. Their extension was the multi-objective consideration. In this way, a fuzzy multiple objective extension for the generalized assignment problem is presented by [START_REF] Tapkan | Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking[END_REF] . For solving this problem, a combinatorial approach consisting of the fuzzy ranking and and bees algorithm was proposed. Additionally, in the uncertainty extensions, the stochastic consideration has been import into the GAP as another extension, for instance, [START_REF] Alaei | The online stochastic generalized assignment problem[END_REF] presented an online stochastic GAP. [START_REF] Sadykov | Column generation based heuristic for the generalized assignment problem[END_REF] also presented a combinatorial method consisting of the column generation, diving heuristic and dual stabilization for the classical GAP. Özbakir et al. (2010) proposed a heuristic composed of a meta-heuristic (bees algorithm) and a ejection chain heuristic for such problems.

In recent years, the literature has been more focused on different extensions of the GAP. In this way, for the Generalized Quadratic Assignment Problem (GQAP), as an extension of the GAP, [START_REF] Mckendall | A tabu search heuristic for a generalized quadratic assignment problem[END_REF] proposed a meta-heuristic tabu search algorithm. They applied GQAP formulation to solve a location problem and assign the machines to different locations. Location/Allocation consideration was studied in the GAP by [START_REF] Ghoniem | Optimization-based very largescale neighborhood search for generalized assignment problems with location/allocation considerations[END_REF]. They developed a heuristic algorithm based large-scale neighborhood search for this problem. Ghoniem et al. (2016a) in another research presented an exact algorithm based on the branch and bound algorithm for their extended version of the GAP. In this year, [START_REF] Sethanan | Improved differential evolution algorithms for solving generalized assignment problem[END_REF] developed a hybrid algorithm composed of three local search techniques which are added to the differential evolution (DE) to solve the classical GAP. Furthermore, the generalized quadratic assignment problem (GQAP) is presented by [START_REF] Mateus | Grasp with path-relinking for the generalized quadratic assignment problem[END_REF] and a combined heuristic integrating the GRASP with path-relinking was proposed.

In fact, all mentioned works consider the generalized task assignments but without considering several consecutive periods of assignment, which has an impact on human factors like working days of the operators. Therefore, the GAP model and corresponding solving methods cannot be applied directly to this problem. An important contribution of this part of our research is the consideration of the availability of the workers and possibility of job rotation in the worker assignment problem. In this way, [START_REF] Alfares | Optimum workforce scheduling under the (14, 21) days-off timetable[END_REF] and [START_REF] Elshafei | A dynamic programming algorithm for daysoff scheduling with sequence dependent labor costs[END_REF] studied the availability of the workers and they considered the restrictions on the working-days and off-days in their workforce scheduling model. Alfares tried to minimize the number of worker regarding the successive working-days and successive off-day for the workers in his research. Then Elshafei and Alfares developed a dynamic model for labor assignment by aiming to minimize the labor costs.

On the other hand, this research can be regarded as a line balancing strategy by the optimal manpower planning. The classical assembly line balancing problem is about the assignment of tasks to the stations of an assembly line, whereas this research is concerned with the assignment of non-identical tasks to heterogeneous workers. Recently various researchers have considered the human resource planning in the line balancing domain. The integration of the assignment problem with the line balancing problem has been introduced by [START_REF] Miralles | Advantages of assembly lines in sheltered work centres for disabled. a case study[END_REF] as an extension of the assembly line balancing problem. In this way, in a research by [START_REF] Vilà | A branch-and-bound algorithm for assembly line worker assignment and balancing problems[END_REF], worker assignment is considered in the line balancing problem in which the efficiency of the workers is the main parameter of assignment. The objective of their research is to minimize the cycle time by reducing the idle time of the stations. [START_REF] Zacharia | A population-based algorithm for the biobjective assembly line worker assignment and balancing problem[END_REF], presented an assembly line balancing problem containing worker assignment. They have proposed a bi-objective model for their combinatorial optimisation problem. A multi-objective evolutionary algorithm (MOEA) has been presented as the solving method. Worker assignment is considered in another assembly line balancing research by [START_REF] Manavizadeh | A simulated annealing algorithm for a mixed model assembly u-line balancing type-i problem considering human efficiency and just-in-time approach[END_REF] in which the workers with different efficiency were classified into four categories. They assumed two type of operators, permanent and temporary, who work in regular and overtime periods. They proposed a simulated annealing approach to solve the line balancing and worker assignment in different steps.

In this way, an integration of the worker assignment and assembly line sequencing and balancing could be seen in the research carried out by [START_REF] Cortez | Sequencing mixed-model assembly lines operating with a heterogeneous workforce[END_REF]. In their work, a sequencing model assembly line was studied in which task execution time depends on the workers. They considered the heterogeneous workers by different skill level and efficiency and also the disabled in their sequencing and assignment model to manage studied assembly line. Minimizing the number of workers in an assembly line balancing problem was targeted in the research by [START_REF] Roshani | Simulated annealing algorithms for the multimanned assembly line balancing problem : minimising cycle time[END_REF]. The same skill level and efficiency have been assumed for all workers and subsequently, the task execution times are not worker dependant. Furthermore, the human aspect have been imposed to the assembly line balancing problem in the research by [START_REF] Chiang | Balancing stochastic two-sided assembly lines[END_REF] in which the tasks duration were assumed to be stochastic because of the worker's efficiency variation. In this manner, the assumption of non-deterministic task execution time depending on skill level of the workers have been taken into account in the research by [START_REF] Zeltzer | Workload balancing and manufacturing complexity levelling in mixed-model assembly lines[END_REF]. Note that, the objective of their research was the levelling and balancing of the workload among the workstations.

In comparison with our research in this thesis, all aforementioned literature did not consider the availability of the workers (working-days and off-days) and also they consider one operator for each station whereas, in the research presented in this thesis, we deal with several workers working in parallel in each station. Another contribution of the research carried out in this thesis is the proposed matheuristic solving approaches for multi-period worker assignment in an assembly line.

2.4/ HUMAN RESOURCE PLANNING IN THE HOME HEALTHCARE

SYSTEMS

Apart from the manufacturing system, the human resource planning in the home healthcare system has also been studied in this thesis. Home healthcare system, as a particular type of the home delivery service systems, is a growing scope of application in the operational research domain. The novelty and complexity of home healthcare operations planning makes it an interesting problem for planning support by Operations Research techniques, particularly the related routing and scheduling problem [START_REF] Rasmussen | The home care crew scheduling problem : Preference-based visit clustering and temporal dependencies[END_REF]). Figure 2.4 shows a home healthcare planning problem which can be viewed as an integration of the worker assignment and vehicle routing problems. FIGURE 2.4 -Human resource planning for a home healthcare system Many various researchers in the optimization domain have worked on such case studies to develop their optimization approaches by taking into account various characteristics and considerations. For instance, [START_REF] Allaoua | A matheuristic approach for solving a home health care problem[END_REF] proposed an integer linear model and a matheuristic approach with a lower bound restriction for the home health-care problem. They studied both aspects of the problem which are routing and assignment concerns, but they did not consider the time dimension. Hence, their model results in a staff assignment to the health-care services for one period of time. [START_REF] En-Nahli | A multi-objective modelling to human resource assignment and routing problem for home health care services[END_REF] developed a multi-objective mixed-integer linear model for the home healthcare planning problem. The preferences of the patients and staffs together with the skill constraints are the considerations which were studied in their research. Cost, workload level, satisfaction level and waiting time are the objectives of their multi-objective model. In their paper the daily needed services are considered to be the same in all of the days. Therefore, the working-days dimension, i.e., the diversity of the needed services in different days is not considered. It was assumed that the resulted planning can be repeated everyday. [START_REF] En-Nahli | Local search analysis for a vehicle routing problem with synchronization and time windows constraints in home health care services[END_REF] modeled the home healthcare routing problem as a Vehicle Routing Problem (VRP), and proposed a combined heuristic algorithm to solve that. Their algorithm consists of an initial heuristic to find a primal solution and a local search with a perturbation operator to improve the solution. Synchronization and tie windows constraints are the main issues which were considered in their study. The home healthcare routing and scheduling problem with synchronized visit and time windows is studied in another research by [START_REF] Frifita | General variable neighborhood search for home healthcare routing and scheduling problem with time windows and synchronized visits[END_REF] in which an extension of the Variable Neighborhood Search (VNS) algorithm was proposed to solve such problems.

Additionally, [START_REF] Fikar | Home health care routing and scheduling : A review[END_REF] and [START_REF] Cissé | Or problems related to home health care : A review of relevant routing and scheduling problems[END_REF] presented two overviews of the recent researches on the home healthcare scheduling and routing problem. The objectives, considerations, constraints, and the solution methods are the different aspects which are investigated in their review. The current studies in this field are well classified based on the planning horizon (single or multi-period). In another similar research, [START_REF] Lin | The therapist assignment problem in home healthcare structures[END_REF] introduced a model for the therapist assignment problem (TAP) in the home healthcare structure by considering the diversity and the workload of the cares, the priority of the patients and the skills of the staff members. They classified the patients and the therapists and proposed a mixed-integer programming model to this assignment problem to maximize the satisfaction rate of demand while meeting the patients' and therapists' preferences. The learning effect and the uncertainty of the care times are two considerations which were taken into account in the HHC model of [START_REF] Errarhout | Two-stage stochastic assignment problem in the home health care[END_REF], where they proposed a stochastic model for the nurse assignment in a HHC structure. The learning effect was added to the model by the reducing time resource consumption during the care through the planning horizon while the experiences gained by giving the cares to the patients. The uncertainty was studied on the resource consumption and their objective was to balance the workload exposed to the nurses by preventing the excessive assignments. [START_REF] Braekers | A bi-objective home care scheduling problem : Analyzing the trade-off between costs and client inconvenience[END_REF] developed a metaheuristic algorithm based on local search heuristic for the daily home care worker routing and scheduling problem. They proposed a bi-objective model for the studied problem : Minimization of the overtime and travel costs and minimization of the patients inconveniences. The preferences of the patients and the time windows for the cares are the additional considerations in their problem. They indicated that the route schedules have an impact on the both objectives. The routes influence the overtime and the total cost in consequence, they also influence the amount of satisfied time preferences and the level of inconvenience in consequence. The home healthcare system is a particular type of the home delivery service system in which the services are the healthcare services. For the workforce planning in this domain, [START_REF] Ehmke | Ensuring service levels in routing problems with time windows and stochastic travel times[END_REF] considered time windows in their home delivery service problem which was modeled as a vehicle routing problem with time windows. They proposed an approach to guarantee the service levels given to all customers while the objective of the problem is the classical VRP objective which is traditional routing costs. Another issue which has been studied in their paper is the stochastic travel times consideration. [START_REF] Goel | Workforce routing and scheduling for electricity network maintenance with downtime minimization[END_REF] considered a human resource planning for a home delivery service system where both routing and scheduling aspects in their workforce planning for the staff members of the electricity network maintenance. Additionally, the home healthcare routing and scheduling problem can be formulated very similar to other optimization problem named "goods assignment and routing planning" in the supply chain management domain where the care services can be regarded as the goods to be assigned and the staffs members can be considered as the vehicles. For such problems, [START_REF] Kuo | Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds[END_REF] developed a model that considers both assignment and routing aspects to minimize the travel times of a distribution system.

2.5/ COMBINATORIAL OPTIMIZATION PROBLEMS FOR MANPOWER PLANNING

Considering that the HHPP is a problem composed of both assignment and routing problems, this part of our research can be viewed as an application of the combinatotial optimization problems. In this domain, many researchers have combined the well-known Operations Research (OR) problems to formulate their studied problems into a mathematical programming model. For instance, [START_REF] Hassanzadeh | Minimizing total resource consumption and total tardiness penalty in a resource allocation supply chain scheduling and vehicle routing problem[END_REF] have modeled a problem of minimization of the resource consumption as an integration of the resource allocation and vehicle routing problems. In the home healthcare domain, [START_REF] Zhang | Manpower allocation and vehicle routing problem in non-emergency ambulance transfer service[END_REF] proposed a combinatorial model to formulate home healthcare problem as a combination of VRP and manpower allocation. Their allocation problem assigns the healthcare vehicles (non-emergency ambulances) to the patients and the VRP part of their model defines the routes for the vehicles. The staff members were regarded as identical and a variable neighborhood search (VNS) algorithm was proposed to solve this optimization problem. Yalçında g et al. ( 2016) modeled the human resource planning in home healthcare services as a combination of the assignment (for the assignment of patients to the staff members), scheduling (for the staff members to visit the assigned patients) and routing (to define the sequence of the visits for each staff member) problems. They proposed a decomposition technique to solve their optimization problem by analyzing various scenarios.

Our problem studied in this part is a variant of the multi-period human resource planning problem in which the assignment of one period has an impact on the next period's assignments. In this domain, [START_REF] Chen | Multi-period technician scheduling with experience-based service times and stochastic customers[END_REF] provide a stochastic model for the multiperiod technician scheduling in which the learning effect and experience of the service workers have been taken into account to assign the tasks of the stochastic costumers to the service workers (technicians) by aiming to minimize the sum of service time and the expected service time for the next period. They formulated this problem based on the markov decision process and solved by employing an approximate approach based on the dynamic programming method. In the multi-period worker assignment domain, [START_REF] Moussavi | Productivity improvement through a sequencing generalised assignment in an assembly line system[END_REF] also proposed a sequencing assignment model for weekly human resource planning in which an assignment was attributed to a day and depended to the previous ones. They proposed two matheuristic approaches to solve their Sequencing Generalized Assignment Problem (SGAP).

The combination of vehicle routing and assignment problems was widely studied in the supply chain and production domain which can be adapted to our service delivery system (home healthcare scheduling). For example, in a research made by [START_REF] Vidal | Implicit depot assignments and rotations in vehicle routing heuristics[END_REF], a multi-depot VRP was presented and enriched by the sequencing choices and depot assignments. For this combinatorial optimization problem, they proposed two metaheuristic approaches, a hybrid genetic algorithm and an iterative local search. [START_REF] Enderer | Integrating dock-door assignment and vehicle routing with cross-docking[END_REF] also developed a model to integrate the vehicle routing and assignment problems in a cross-docking optimization problem in which a assignment of the trucks to the doors of cross-dock terminals is combined with the designing of the routes for the vehicles. The objective of their model was to minimize the material handling and transportation costs which are the classical objectives of the VRP. They proposed a column generation algorithm to solve this combinatorial optimization problem. In this domain, a combination of the VRP and scheduling problem with synchronization and precedence considerations was proposed by [START_REF] Bredström | Combined vehicle routing and scheduling with temporal precedence and synchronization constraints[END_REF]. For the integration of the vehicle routing and scheduling problems in the production domain, [START_REF] Moons | Integrating production scheduling and vehicle routing decisions at the operational decision level : A review and discussion[END_REF] provided a review and classification study on the existing literature. The characteristics and considerations of the models and the proposed objective functions were reviewed in their research. In this domain, [START_REF] Corréa | Scheduling and routing of automated guided vehicles : A hybrid approach[END_REF] proposed a hybrid method consisting of a constraint and mixed-integer programming to solve an integrated model composed of the scheduling, assignment and vehicle routing problems. Another variant of the VRP which is very close to the HHS problem is presented by [START_REF] Spliet | The discrete time window assignment vehicle routing problem[END_REF] as the discrete time window assignment vehicle routing problem (DTWAVRP) in the distribution networks. The assignment part of their problem aims to assign a time window to each customer, and the VRP part is to construct the vehicle routes by satisfying the assigned time windows. They proposed a two stage stochastic approach to optimize this problem.

About the solution approaches for such problems (VRP with time windows), many researchers developed different heuristics, metaheuristics and exacts approaches. For instance, [START_REF] Miranda | The vehicle routing problem with hard time windows and stochastic travel and service time[END_REF] proposed a metaheuristic based on an iterative local search algorithm by aiming to minimize travel and operating costs. [START_REF] Dalmeijer | A branch-and-cut algorithm for the time window assignment vehicle routing problem[END_REF] de-veloped a branch and cut approach by considering two optimization aspects : assigning time windows and routes planning for the vehicles. [START_REF] Baker | Extensions to the generalised assignment heuristic for vehicle routing[END_REF] proposed a heuristic approach based on the generalized assignment formulation to solve the vehicle routing problem. They decomposed the VRP model to the generalized assignment problem (GAP) and the travel salesman problem (TSP) and employed the generalized assignment heuristic presented by [START_REF] Fisher | A generalized assignment heuristic for vehicle routing[END_REF] to solve the first part of their approach.

Another consideration of the studied problem is the number of working-days and off-days restrictions for the staff members which has been taken into account for the various workforce scheduling models in the literature (Özgüven et al. (2013), [START_REF] Narasimhan | An algorithm for single shift scheduling of hierarchical workforce[END_REF]). This issue is considered in another model on the workforce scheduling problem presented by [START_REF] Moussavi | Reducing production cycle time by ergonomic workforce scheduling[END_REF] where the adequateness level of the heterogeneous workers (the efficiency of the workers) on different tasks is the basis of the assignment. The objective of their model was to minimize the total task time.

2.6/ CONCLUSION

In this section of the thesis, a state of the art for the different aspects of the studied problem has been presented. The next sections present the studied problems, methodology, mathematical models and the proposed algorithms together with the numerical applications and experimental and computational results.

The rest of this thesis is organized as follows : in the first part, a human resource planning by ergonomic considerations in a manufacturing system is modelized mathematically. According to the structure of the studied system, the manpower planning is formulated by applying the generalized assignment problem in the second part. A novel variant of this well-known operations research problem is introduced in this part. A hybrid heuristic and two matheuristic approaches are proposed in this thesis to solve the GAPs. In the third part, human resource planning by using GAP formulation is developed for a home healthcare system. Another contribution of the GAP is presented in this part where an integration of the GAP with the Vehicle Routing Problem (VRP) is developed. A matheuristic approach is proposed to solve this combined optimization problem.

ERGONOMIC WORKER ASSIGNMENT

FOR PRODUCTIVITY IMPROVEMENT

3.1/ INTRODUCTION

Considering the ergonomic factors in the worker assignment and job rotation planning, may be an effective strategy to increase the worker satisfaction and motivation as well as the efficiency of the workers. Most of the recent researches in this domain focus on the on the minimizing the ergonomic risk and hazard, whereas the characteristics of the workers were not sufficiently considered. As an ergonomic research, in this study, the worker assignment is performed according to the ergonomic adequation between characteristics of jobs and operators features. In this way, all of the workstations are analysed to determine the ergonomic requirements of jobs. On the other hand, the operators characterization are explored. There are various criteria in the ergonomic analysis of job and operator but in this study, four commune ergonomic factors are concurrently considered to compare the job requirement and worker capacity and measuring the adequation level between them.

It is not possible to obtain an exact value for some ergonomic factors because of being qualitative. For this reason, they must be estimated by fuzzy, probabilities or other uncertain approaches. In this research utility function is applied to determine the adequation level between jobs and operators. These values might be used as efficiency index of operators for performing each job. In an experimental research, we proved that this efficiency index affects the operation time of the job. In this part of our research, we intend to reduce the production cycle time by an effective job assignment considering the ergonomic criteria and adequation between workstations and workers. Note that this assignment is not constant for all of the planning days. The workers positions may be changed from one day to another. This approach is applied to a part of a automotive assembly line consists of 5 workstations with 9 daily required workers and 13 available workers.

3.2/ METHODOLOGY

A novel approach based on ergonomic criteria is proposed for evaluation of the jobs and operators to estimate the ergonomic adequation level between work and worker. For this, we consider 4 essential ergonomic factors to analyse. Comparison of job requirement and operator capacity is done for each factor by using the utility function. As a result, 4 utility functions is achieved and in the next step by determination an importance weight for each criterion, a global utility function is obtained for estimating the conformity level. Job assignment is realized by considering these accumulated values as the performance indices. Note that, in the experimental sampling, it has been proved that these values have a relationship with the operation times.

3.2.1/ ERGONOMIC ANALYSIS ON THE JOBS AND THE WORKERS

There exist many various ergonomic factors in the manufacturing. In one of the most commune categorization, they are classified into three general types as following :

-Cognitive : Intellectual workload, skill level in decision-making, learning and forgetting... -Physical : Anthropometry and other features relevant to the physical activities such as force. -Organizational : Capacity of teamwork and communication, management the quality and resources...

In this study, according to the case study and from the point of view of the experts, 4 most relevant criteria are analysed in a manufacturing system. 1.Height, which is one of the most important anthropometric criteria, 2.Age. Most of the ergonomic factors have a relationship with that. 3.skill level, which is related to the both of the cognitive and organizational aspects. and 4.experience level, that is almost an organizational factor of ergonomics. At the beginning, an ergonomic evaluation must be done on the workstations. Two following questions must be answered after this evaluation.

Which criteria have a significant impact on the performance and productivity of process ?

What level of each criterion is required for performing the tasks ?

In our case, this assessment is performed by analysing the working place, questionnaire and also using the classified information from the experts. Consequently, a table of jobs requirements for the system under study (consisting of 5 workstation), is achieved (table 3.1). Note that for skill level criterion, there exists an evaluation test for each job, with a score between 0 and 10, and the experience level is evaluated based on the number of years of experience. After evaluation of the jobs and operators, separately, we have to define a systematic approach to determine the adequation level between two above mentioned tables (3.1,3.2). Adequation values, as a performance index, denotes the conformity of each operator in each job. Subsequently, by using the information from the experts, a linear utility function is defined for each ergonomic factor. Linear utility function is a simplified model of quasi-concave utility function. In this way, 3 intervals is determined for each parameter : 1.forbidden, 2.acceptable and 3.excellent intervals. Utility functions (U) of "Height" at workstation 2 (172 ≤ H ≤ 183),as an example, is defined as follows :

Ergonomic characteristics needed by the jobs

Ergo factor WS1 WS2 WS3 WS4 WS5 Height (cm) - 172 ≤ H ≤ 183 H ≥ 170 - 165 ≤ H ≤ 178 Age (year) - 25 ≤ A ≤ 35 - A ≥ 30 28 ≤ A ≤ 45 Skill level (score) A ≥ 8 A ≥ 5 A ≥ 6 A ≥ 8 A ≥ 5 Experience level (year) E ≥ 5 - E ≥ 3 E ≥ 7 E ≥ 4
U(h) =                    0 if h < 168 or h ≥ 190 1 -172-h 172-168 if 168 ≤ h < 172 1 if 172 ≤ h < 183 1 -h-183 190-183 if 183 ≤ h < 190 (3.1)
As shown in figure 3.1, by applying the utility function, the conformity level of the operators for each job is calculated. This figure is corresponded to only "height" parameter. Similarly, for 3 other factors, the relevant functions are defined. As a result, in each factor for each operator a conformity value at each job is determined. Now for making a decision about the conformity between operators and jobs, All four analysed parameters must be combined. This will be possible by assigning the weights to the parameters. Defining an accumulated function (equation 3.2) on the utility values obtained in the previous section, realizes the global conformity level. Table (3.3) shows the result of this mixed utility function by considering the same weights for all the criteria. In this function, W h , W a , W s , W e denote the weights of the parameters, and U h i j , U a i j , U s i j , U e i j , U total i j , indicate, respectively, the utility value of "height", "age", "skill level", "experience level" and "global utility value" of operator i for workstation j. Final step of the proposed approach, is the assignment of jobs to the operators. This assignment is not directly based on the utility values ; whereas it is based on the operation times of operators on the workstations. For evaluation of the impact of utility value on the operation times, we applied the simple random sampling method in a production line. Afterwards, linear regression has been used to estimate the function of operation times based on the utility values. The objective is to minimize the production cycle time by an efficient ergonomic job assignment. In the next section, a mixed integer mathematical model is presented to solve this allocation problem.

U total i j = W h U h i j + W a U a i j + W s U s i j + W e U e i j (3.2)

Global utility level

3.3/ PROBLEM DESCRIPTION

Ergonomic worker assignment problem focuses on the evaluation of the jobs (requirements) and the operators features to assign the jobs to the workers according to the most adequation between jobs and persons from the ergonomic point of view. In a system that works all of the days in a week and with the workers who works 4 or 5 days per week, workforce size must be more than the daily number of required workers. The number of available workers for weekly job assignment in this system is predetermined. By regarding to the ergonomic efficiency index of the workers in different workstations (using 4 popular ergonomic factors in manufacturing), the jobs are assigned to the operators.

This allocation is not a static one because of workday limitation of the workers (4 or 5 days per week) and industrial workday requirement (7 days per week). Thus, in the production planning, the positions of the workers are changed regarding to their availability.

On the other hand, the ergonomic efficiency index have a considerable impact on the operation time of the jobs ; The main objective is to reduce the production cycle time by most adequate assignment (ergonomically) of jobs to the workers. Because of dynamic in the model (position of the workers), the production cycle time in different days, will be different. Thus the output of the model is optimum weekly workforce schedule, such that the total daily production cycle time in a week would be minimized. Indirect aim of the problem is to maximize the number of production units per week.

3.4/ MATHEMATICAL MODEL

Mixed integer linear programming can be a competent approach to formulate the ergonomic job allocation problems. The objective of the model is the minimization of the daily production cycle time in a week through an effective job assignment by satisfying the process and operations schedules and ergonomic limitations of the workstations. The other conditions of the problem is as the following :

-Each worker can be assigned to only one job in each day.

-Each worker must be assigned to work for a limit number of days in planning period. -The number of required workers for each workstation must be satisfied every day.

-The jobs can be started once all of the workers in the preceding workstation complete their tasks. -A worker can be assigned to a job if his efficiency for the job would be more than the permissible limit.

The assumptions of the model are as the following :

-The number of operators required by different workstations are not necessarily equal. -The number of available workers for assignment is predetermined.

-The number of days that the operators can work, are either 4 or 5 days per week and manager (system) decides about that. -The starting times for all operators in a workstation are simultaneously .

3.4.1/ COMPONENTS OF THE MODEL

The Parameters of the model are as the following :

-D max maximum number of days that operators are authorized to work in a week ;

-D min minimum number of days that operators have to work in a week ; n number of available workers ;I = {1, ..., n} m number of workstations ; J = {1, ..., m} k number of days in planning period ; D = {1, ..., k} -A j minimum operation time in workstation j ; -B j maximum operation time in workstation j ; -N j number of workers required in workstation j ; -E omin j permissible limit for efficiency of individuals to work in workstation j ; -E wmin j permissible limit for average efficiency of workers who work simultaneously in workstation j ; -E i j efficiency of worker i in workstation j ; And the variables of the model are :

-C : sum of the daily production cycle time in a planning period ; -X d i j = 0 -1 binary value where X d i j = 1 if operator i is assigned to the workstation j in the workday d, and 0 otherwise ; -Z i = the number of day that operator i works ; -O d i j = the operation time of operator i in the workstation j in the workday d ; where

O d i j = 0 if X d i j = 0 , and O d i j > 0 if X d i j = 1. -S d j =

3.4.2/ MODEL FORMULATION

A linear minimization objective is formulated for the problem and the constraints which must be respected are presented as follows.

Minimize C = k d=1 C d (3.3) subject to : m j=1 X d i j ≤ 1 ∀i ∈ I, d ∈ D (3.4) Z i = m j=1 k d=1 X d i j ∀i ∈ I (3.5) n i=1 Z i ≤ D max ∀i ∈ I (3.6) n i=1 Z i ≥ D min ∀i ∈ I (3.7) n i=1 X d i j = N j ∀ j ∈ J, d ∈ D (3.8) O d i j = B j -E i j B j -A j X d i j ∀i ∈ I, j ∈ J, d ∈ D (3.9) O d i j ≤ P d j ∀i ∈ I, j ∈ J, d ∈ D (3.10) F d j = S d j + P d j ∀ j ∈ J, d ∈ D (3.11) S d j+1 ≥ F d j ∀ j ∈ J, d ∈ D (3.12) C d ≥ F d j ∀ j ∈ J, d ∈ D (3.13) E i j -E omin j X i j ≥ 0 ∀i ∈ I, j ∈ J (3.14) n i=1 E i j X d i j ≥ N j E wmin j ∀i ∈ I, j ∈ J, d ∈ D (3.15) X d i j ∈ {0, 1} , Y i j , Z i ≥ 0 integer (3.16) S d j , W d j , F d j , K d i j ∈ R + (3.17)
The objective of the model is to minimize the sum of the daily production cycle time in the planning period. In the model, workforce schedules are determined by X d i j decision variables, which are binary. They show whether operator i is assigned to workstation j in workday d, (X d i j = 1), or not (X d i j = 0). The first set of constraints (3.4) ensure that each operator is assigned to maximum one workstation in each workday. Equation (3.5) shows the total number of days that each operator works during the planning period, while (3.6 and 3.7) indicate that each worker has to work 4 or 5 days per week. Constraints (3.8) define the number of workers required for each workstation. Constraints (3.9) calculate the operation time of each worker (for producing one product) which is depended on his efficiency in the workstation in which he works ; where it takes a positive value if mentioned worker is assigned to the intended position, otherwise its value would be zero. Constraints (3.10) describe the relationship between operation time of each worker and the processing time of the workstation which is the maximum operation times of the workers who work in the considered workstation. Constraints (3.11) define the relationship between starting, processing and ending times of a production cycle time in each day, where the precedences necessities between workstations are provided by constraints (3.12). By constraints (3.13) the production cycle time in each day can be calculated which is the maximum values of the ending time of the jobs. Two set of constraints (3.14) ensure that the efficiency of the individuals who work in the workstations are more than the individual permissible limits. Note that, according to the constraints (3.15), the average efficiency of the operators who work simultaneously in the same workstation in the same day must not be less than permissible limit.

3.5/ APPLICATION ON THE CASE STUDY

An assembly line consisting of 5 workstations (WS1,...,WS5) is considered as a numerical application. This system must work seven days a week (D1,...,D7). The number of required workers at different workstations are not identical. The system has 13 available operators (O1,...,O13) and each one has a specific utility level at each workstation (like table 3 but for 13 operators). The procedure of the calculation of these values was explained in section 3.2.

The operation times at certain workstations (WS2, WS3, WS5) depend on the utility level of the operator who performs them. Whereas other workstations (WS1, WS4), the performance of the worker does not affect on the processing time (for example, an automated workstation). The processing time and number of required workers at different workstations are presented in table 3.4. The operators must work four or five days in a week. The planning is defined for a duration of one week. In this workforce scheduling each operator is able to change his job from a day to another. But they are not authorized to change that during a workday.

The case study is a continuous production system in which all of the operators in the same workstation, start their works simultaneously, once the latest worker of the preceding station completes his task. Note that, the operation time of the operators at the workstations in which the processing times are changeable (WS2, WS3, WS5), is linearly varied based on the performance of the operator (as shown in table 3.4).

Workstations' properties and Processing times

No. of operators

Processing times Type WorstU i j BestU i j Relevant linear Function WS1 1 constant 5 mins 5 mins

F(U i1 ) = 5 WS2 3 changeable 10 mins 6 mins F(U i2 ) = 10 -(4 * U i2 ) WS3 2 changeable 6 mins 3 mins F(U i3 ) = 6 -(3 * U i3 ) WS4 1 constant 4 mins 4mins F(U i4 ) = 4 WS5 2 changeable 7 mins 5 mins F(U i5 ) = 7 -(2 * U i5 ) TABLE 3.

-Workstations' properties and Processing times

In table 3.4, U i j and F(U i j ) denote, respectively, the performance (utility) and the processing time of worker i working at workstation j. As a result we obtain a table similar to the table 3.3 which shows the operation time of each operator in different workstations. By using the values of this table, the workers are assigned to the workstations with the aim of reducing total processing time (makespan).

For solving this assignment problem, a mixed integer mathematical model, as explained in detail in section 3, is proposed. An optimization software named GUROBI has been employed to solve the problem. The optimal workforce schedules for a weekly production planning is shown in table 3.5 (PCT : production cycle time). As can be seen, the assignment of the workers, varies from a day to another. It happens because of the limitation on the number of workdays for the operators (they must work only 4 or 5 days in a week). As an example, figure 3.2 illustrates the job assignment to the workers in the sixth workday (D6). The workers assigned to different workstations and their operation times are shown in this figure. The result of the optimal solution, in comparison with an random assignment, reduces largely the production cycle time in each workday. The proposed approach has been tested for 20 simulated instances consisting of 5 to 9 workstations and the computational results is shown in table 3.6. (2016) are the basis of the decision about dynamic job assignment which is ergonomic adequation level between job and worker as well as the basis of the job rotation which is the availability of workers. Besides, the objective is to minimize the sum of the daily makespan and proposed approach has been applied in a combined system consisting of the parallel and consecutive tasks.

Weekly workforce schedule

D1 D2 D3 D4 D5 D6 D7 Avg ET WS1 O11 O6 O13 O7 O11 O7 O7 5 WS2 O1/O9/O10 O1/O9/O12 O2/O10/O12 O1/O9/O12 O1/O9/O12 O1/O9/O10 O2/O10/O12

Computational results

No of WS No of OP per day

3.6/ CONCLUSION

This chapter proposes an approach for ergonomic job assignment by determination of the ergonomic adequation level between workers and workstations in a manufacturing system. For this purpose, a mixed integer mathematical model is presented and solved. Its objective is to minimize the average of daily production cycle times for a given planning period by an appropriate job assignment. The model generates the optimal daily rotating workforce schedules during the planning period by respecting all of the operator limitations and workstation and production constraints. On the other side, for determination of adequation level, the personal capacities of the workers and also workstations requirements is considered. Ergonomic factors are applied for evaluation of the workstations and operators and linear utility functions are employed for determination of efficiency the operators in the jobs.

The numerical application illustrates that the ergonomic considerations in the job assignment has an important impact on the production cycle time. Additionally, the results of the presented strategy in workstation and operator evaluation phases, show that the processing times at the workstations are highly depended on the ergonomic capacities of the operators. Consequently, ergonomic operator characterizations give us more benefits for an efficient job assignment. As a result an ergonomic workforce schedule consisting of job assignment and rotation for a planning period is constructed. It determines which worker performs which job in which workday in an optimum manner. The idle times and ergonomic risks can be considered as the futures works of the proposed approach.

JOB ROTATION SCHEDULING FOR WORKLOAD BALANCING In the automotive assembly line, there are generally several sectors which is considered as a small factory including numerous workstations. A sector is then divided into several team that is a small organizational unit consisted of 4-7 members. Similarly, the jobs are grouped into several workstations and a team is assigned to a workstation. Each team has its own team leader who plan the rotations of the operators. The team members rotate between jobs within a workstation. Job rotations were scheduled because the assembly line required high flexibility as the operators have to be qualified to work at any job. Team rotation schedules were performed manually by the team leader without considering workloads and risk factors for an operator at different jobs. Therefore, the variance in cumulative daily workloads was high between the team members, and an operator might expose to the sequential high workloads by the job rotation. The cycle time to perform all the tasks in a workstation was 6 minutes. There were three pauses during the day and the operators of a team rotate between jobs after each break. This means that each operator works at four different jobs over one work shift.

A distinguishing characteristic of the job rotation in the studied system in comparison with the classical job rotation is as follows : In the classic job rotation all of the workers must be able to perform all the jobs which cause difficulty in term of cost and time for learning an executing model in a system. Whereas, job rotation within a group which consist of a specified number of jobs reduces significantly cost and time spending for learning. The aim of this field study is to develop a mathematical model applicable in a real-world setting to balance the physical workload in a production assembly and to minimize sequential high workloads during a daily job rotation.

4.1.2/ ERGONOMIC ANALYSIS OF WORKSTATIONS BY SES METHOD

An in-house ergonomic method for automotive assembly line, called SCANIA Ergonomic Standard (SES), is employed to analyze the workstations and determined physical workloads [START_REF] Zare | Evaluation of ergonomic physical risk factors in a truck manufacturing plant : case study in scania production angers[END_REF]). This field method integrates 20 ergonomic parameters (Table 33 4.1), which are grouped into five categories including repetitiveness, working posture, force, manual handling and energy consumption [START_REF] Zare | Evaluation of ergonomic physical risk factors in a truck manufacturing plant : case study in scania production angers[END_REF]).

Ergonomic parameters measured

Main category

Sub-category Risk factors Therefore, the widespread ergonomic factors were measured to define the parameters and the objective functions of the mathematical model for job rotation schedules. Weights of objects, magnitude of forces (dynamometer), and handle diameters (caliper) were also measured. The results were classified according to a traffic light system : the normal or green level indicating an acceptable situation with minimal risk of WR-MSDs ; the yellow level indicating a moderate workload, and the red level corresponding to situations at high workload. After studying each ergonomic criterion for a workstation, the numbers of green, yellow and red criteria determined the final workload of that workstation (Table 4.2).

Prioritization of risk factors and workloads

Methods

Evaluation Criteria Green Yellow Red This color-coded method is based on Swedish guidelines and it has been used in other observational methods particularly in the car industries [START_REF] Berlin | Corporate-internal vs. national standard-a comparison study of two ergonomics evaluation procedures 131 used in automotive manufacturing[END_REF][START_REF] Törnström | A corporate workplace model for ergonomic assessments and improvements[END_REF]). Considering 20 ergonomic parameters evaluated by the in-house ergonomic method in a mathematical model provide a complicated model, non-applicable to a real-world setting. We, therefore, developed a method of aggregation which 20 parameters were categorized in five main parameters such as work posture (composed of 11 ergonomic criteria), repetition, force (composed of 3 ergonomic criteria), material handlings (composed of 2 ergonomic criteria), and energy consumption (composed of 3 ergonomic criteria)(MAHMOUDABADI ( 2015)). Following this logic, the final workload was attributed to the main criteria, and they were considered as the parameters of the mathematical model to make the decision about the job rotation schedules (Table 4.3).

For solving the mathematical model of job rotation, we need a numerical score for each color to be able to balance the global workload among the operators. To obtain the numerical ratio for the workload colors, a statistical analysis is carried out as explained in the following.

4.1.3/ NUMERICAL EVALUATION OF WORKLOADS

The Swedish guideline which is presented in table 4.2 is employed to translate the traffic light level (green, yellow, red) into numerical values. In this way, a mathematical analysis is undertaken as follows.

The parameters of this analysis is presented as : n(g), n(y), n(r) : The number of analyzed criteria in each job with respectively, green, yellow and red workload. Note that twenty ergonomic criteria are analyzed to evaluate the workload of each job (n(g) + n(y) + n(r) = 20).

As shown at the first line of the table 4.2 (number of yellows), the relevant equation is as :

WL j =              i f n(y) ≤ 8 =⇒ G elsei f 9 ≤ n(y) ≤ 16 ⇒ Y else (n(y) ≥ 17) =⇒ R (4.1)
And in the second line of the table (number of reds) we have :

WL j =              i f n(r) ≤ 6 =⇒ G elsei f 7 ≤ n(r) ≤ 9 ⇒ Y else (n(r) ≥ 10) =⇒ R (4.2)
Finally, the third line (number of reds + number of yellows) can be presented as :

WL j =        i f n(y) + n(r) ≤ 16 =⇒ G else (n(y) + n(r) ≥ 17) =⇒ R (4.3)
According to the third line of the first equation, once we meet 17th yellow criteria, the red color is attributed to the job as the global workload level instead of yellow. Similarly, in the third line of the second equation, the yellow color is replaced by the red while the 10th red criteria is met. It can be concluded that 17 yellow criteria have the same impact as 10 red criteria. Therefore, the ratio of the severity of the red to yellow workload can be estimated as follows :

17 × S (Y) 10 × S (R) =⇒ S (R) S (Y) = 17 10 = 1.7 (4.4)
Hence, the red workload is 1.7 times more severe than the yellow color.

To calculate the severity ratio of the green workload, a normalization is required because the parameters are dependent on each other. By considering that more than 90% of the analyzed jobs contain at least four green criteria, it is assumed that the number of green criteria at all of the jobs are equal or greater than 4 (n(g) ≥ 4). Therefore, according to the equations (4.1, 4.2, 4.3) :

I f n(g) ≥ 11 ⇒              n(y) n(r) n(y) + n(r) ≤ 9 =⇒ WL j R (WL j = {G or Y}) (4.5)
This condition formula signifies that at least 11 green criteria are needed to ensure that the workload color of the job is not red. On the other hand, the proposed normalization (n(g) ≥ 4) implies :

I f n(y) ≥ 7 ⇒        n(r) ≤ 9 n(y) + n(r) ≤ 16 =⇒ WL j R (WL j = {G or Y}) (4.6)
As a consequence of the above mathematical analysis, 7 yellow criteria are needed to be sure that the red workload is not assigned to the job. Therefore, seven yellow criteria have the same impact as eleven green criteria to prevent the red workload being attributed to a job. It means that :

11 × S (G) 7 × S (Y) =⇒ S (Y) S (G) = 11 7 = 1.57 (4.7)
In this research, the severity of the green color as the basis of the workload amount is considered to be 1. As a result :

       S (Y) S (G) = 1.57 S (R) S (G) = S (R) S (Y) × S (Y) S (G) = 1.7 × 1.57 = 2.67 =⇒              S (G) = 1 S (Y) = 1.57 S (R) = 2.67 (4.8)
A severity score is calculated for each workload color by above mathematical analysis. It must be noted that, this analysis has been validated and proved by the engineers and the experts of the studied company.

The proposed calculations are to attribute a numerical score to the workload severity of a criterion in a job. For the global workload of a job, the severity score is estimated by the sum of the workload scores of the analysed criteria. The numerical daily workload on the operators is estimated by the sum of the workload scores of the jobs to which they are assigned during the day. (table 4 The balancing of the daily workload on the workers in an assembly line is targeted in this research. The workers are exposed to the workload by working at the heterogeneous jobs with different workloads. The difference between workload levels of the jobs persuades us to employ job rotation to smooth and minimize the ergonomic risks on the workers.

In the case study, the workers are not able to do all of the jobs. They are only skilled for the jobs which are placed in one workstation. Hence, the job rotation is implemented on the workers of the same group. As mentioned above, a group is a number of workers who work at the jobs of the same workstation. In fact, the workers are assigned to the workstations and the job rotation is developed into the workstations. Note that, the workers can not change their workstation (group) during the planning horizon. The planning horizon is a predefined number of days and each day contains four working periods of two hours (Two periods in the morning and two in the afternoon). The rotations take place during the break time between two periods. To find the optimum job rotation planning on the presented system, the problem is modeled mathematically. Actually, a mixed-integer linear programming is proposed to model the studied job rotation problem. The objective of the model is to minimize the maximum daily workload which is exposed to the workers.

The daily workload on a worker is equal to the sum of the workloads of the jobs which are performed by him during the different periods of the day. In the job rotation model, the ergonomic restrictions which must be respected are as the following :

-The assignment of two consecutive high workload jobs to a worker during a day must be prevented. -The assignment of two jobs, with the high workload in the same criterion, consecutively to a worker during a day must be prevented. A mathematical model is composed of the parameters and the variables, and it is formulated by the objective function and the constraints. The proposed model for the studied problem is as the following.

4.2.1/ COMPONENTS OF THE MATHEMATICAL MODEL

PARAMETERS

The parameters of the model which must be identified before solving the model, are presented as :

-Q jl : Workload of type l 1 that a worker is exposed by working one period in job j, where Q jl = 1, 1.57 or 2.67 if job j has a, respectively, Green, Yellow or Red workload of criterion l. -H j : Global workload of job j, where H j = 1, 1.57 or 2.67 if the global workload of job j is, respectively, Green, Yellow or Red. -

VARIABLES

The variables are obtained by solving the model, and they identify the objective value and its related outputs. The decision variables of the model are presented as :

1. Workload of type l implies the workload score related to criterion l -X i jpd : binary, where X i jpd = 1 if worker i works at job j in period p of day d, and 0 otherwise ; -Z ilpd , Y ilpd , V ilpd : binary variables, where Z ilpd = 1 if worker i is exposed to the high workload, Y ilpd = 1 if worker i is exposed to the medium workload and V ilpd = 1 if worker i is exposed to the low workload of type l in period p of day d. -C ipd , B ipd , A ipd : binary variables, where C ipd = 1 if worker i works at a job with the high global workload, B ipd = 1 if worker i works at a job with the medium global workload and A ipd = 1 if worker i works at a job with the low global workload in period p of day d ; -F id =Total score of the workloads to which worker i is exposed during day d ;

4.2.2/ MODEL FORMULATION

The formulation of the mathematical model is composed of the objective function and the constraints. The objective function of our model aims to balance the daily workload on the workers and presented as follows :

Minimize Z = Max i,d F id (4.9)
The constraints of the proposed model consider the conditions of the assignment problem, job rotation problem, and the capability of the workers with a special attention to the ergonomic aspect. These conditions are presented and explained below.

m i=1 X i jpd = 1 ∀ j ∈ J, p ∈ P, d ∈ D (4.10) n j=1 X i jpd = 1 ∀ i ∈ I, p ∈ P, d ∈ D (4.11) t p=1 n j=1 r l=1 W l Q jl X i jpd = F id ∀ i ∈ I, d ∈ D (4.12) Q jl X i jpd = αZ ilpd + βY ilpd + γV ilpd ∀ i ∈ I, j ∈ J, l ∈ L, p ∈ P, d ∈ D (4.13) Z ilpd + Y ilpd + V ilpd = 1 ∀ i ∈ I, l ∈ L, p ∈ P, d ∈ D (4.14) Z ilpd -V il(p+1)d ≤ 0 ∀ i ∈ I, l ∈ L, p ∈ P, d ∈ D (4.15) H j X i jpd = αC ipd + βB ipd + γA ipd ∀ i ∈ I, j ∈ J, p ∈ P, d ∈ D (4.16) C ipd + B ipd + A ipd = 1 ∀ i ∈ I, p ∈ P, d ∈ D (4.17) C ipd -B i(p+1)d -A i(p+1)d ≤ 0 ∀ i ∈ I, p ∈ P, d ∈ D (4.18) K g +K g+1 K g +1 X i jpd + K g +K g+1 K g +1 X i j(p+1)d = 0 ∀ g ∈ G -, i ∈ I, j ∈ J, d ∈ D, p ∈ P - (4.19) K g +K g+1 K g +1 X i jpd + K g +K g+1 K g +1 X i jp(d+1) = 0 ∀ g ∈ G -, i ∈ I, j ∈ J, p ∈ P, d ∈ D - (4.20) X i jpd , Z ilpd , Y ilpd , V ilpd , C ipd , B ipd , A ipd ∈ {0, 1} , Q jl , H j ∈ Integer + , W l ∈ R + (4.21)
Equation ( 4.9), as the objective function of the model, is to balance the workload by minimization of the maximum daily workload to which each one of the workers is exposed.

The two fist sets of constraints (4.10,4.11) are related to the assignment aspect of the studied problem and ensure respectively that each of the jobs in every period is assigned to the one and only one worker and each one of the workers is allocated to the one and only one job every period. By constraints (4.12), the amount of the daily workload on the workers "F id " is calculated. This score is obtained by the weighted sum of the workload scores of different types which are exposed to the worker during different periods of the day. The two next sets of constraints (4.13,4.14) determine the score of the workloads of different types on the workers where in each period of time, one of the three binary variables Z ilpd ,Y ilpd or V ilpd is equal to 1 and implies respectively the worker i is exposed to the high, medium or low workload of type l in period p of day d. The constraints (4.15) represent one of the ergonomic conditions which are considered in this problem and ensure that if a worker is exposed to the high workload of type l in a period, in the next period he must be allocated to a job with low workload of type l. By the constraints (4.16,4.17), three binary variables are attributed to the global workload level of the jobs. These variables represent the global workload level that each one of the workers is exposed during a period. Note that, for each worker, in every period only one of the binary variables C ipd , B ipd or A ipd is equal to 1. Another ergonomic condition is imposed on the model by constraints (4.18) where they guarantee non-assignment of two consecutive high workload jobs to the workers. It means a high workload job must be followed by a medium or low workload one for a worker during a day. The two sets of constraints (4.19,4.20) are related to the job rotation inside of the workstations (teams) and ensure that the workstation assigned to the the workers is unchangeable from a period to another and from a day to another.

4.3/ NUMERICAL APPLICATION

The ergonomic analysis which was presented in section 4.1.2 and 4.1.3, and the proposed job rotation mathematical model (section 4.2) are employed to develop a platform for the ergonomic job rotation in an automotive assembly line. In this research, a specific part of this production system containing three workstations and fourteen jobs is studied where four jobs are placed in the first workstation and the number of jobs in the second and third workstations is five. As mentioned before, to perform the job rotation inside the workstations, all of the the jobs are analyzed by 20 ergonomic parameters. These parameters are grouped into five main ergonomic criteria as the Repetition, Posture, Material handling, Force and Energy consumption. The job rotation is programmed based on these five criteria. This normalization is performed to simplify the solving of mathematical model.

The results of the ergonomic evaluation of the studied jobs which are shown in table 4.3, are used as the parameters of the job rotation model. In this table, the workload score of each job is estimated by the sum of the workload amounts of the individual criteria. It can be seen that the difference between workloads of the jobs is not negligible. For instance, the estimated score for job 10 is equal to 10.56 where three of five ergonomic criteria have a high workload, whereas the score of job 6 which is 5.57 and it has a low workload in all of the ergonomic criteria. These significant differences persuade us to apply job rotation strategy to reduce the risk of MSDs and occupational diseases on the operators who work at the high workload jobs. Note that, the workload score of the jobs is calculated for an operating duration of two hours. As mentioned before, the working day of the studied system contains four periods of two hours. Therefore, if one operator works at the job number 10 all of four periods during a day, he is exposed to a workload score of 42.32.

The main objective of this research is to minimize (balance) the daily workload score on the operators by employing the proposed job rotation model. Moreover, the mathematical approach avoids the risk of assigning two successive high workload jobs to an operator during a day. This consideration is imposed on the model as an ergonomic constraint. The model is solved for the studied production system by using the parameters presented in In this research, the workers are considered to be identical, but the only difference between them is their skills for working in different workstations. Table 4.5 presents the capability of the workers where worker 1 (op1) is skilled for workstations 1 and 2, worker 2 for only workstation 2 and worker 9 is able to work at all of the workstations. and14). The results present the optimal worker assignment to the jobs, also the periodic and cumulative workload scores to which each operator is exposed during a day. By applying the proposed worker assignment, the cumulative (daily) workload scores for all workers in workstation 1 are identical and equal to 30.75 ; These scores in workstation 2 vary between 29.61 and 30.14 ; For workstation 3 vary from 34.05 to 34.58. As a result, the physical workload are well propagated among the operators where in each workstation, their variations have been enormously became slight (in comparison with table 4.3). The workload propagation before and after job rotation is presented in figure 4.1.

Capability of the workers

FIGURE 4.1 -Comparison of dispersion of the workload by and without job rotation

In the figure, the color filled bottoms show the physical workload levels before applying job rotation and hatching filled bottoms display the workload levels by applying job rota-tion inside the workstations. As can be seen, in every workstations, the variation of the workloads between the operators is highly decreased after job rotation.

Afterwards, a statistical analysis has been performed to obtain the practical information about the dispersion of the workloads . In this analysis, the workload scores are analyzed by employing two most important statistical factors as "mean" and "standard deviation" and the results are shown in table 4.6. As seen in the table, the mean of the workload in each workstation does not vary by job rotation but the standard deviations are greatly decreased.

Statistical analysis of the impact of the rotation

As an example, the standard deviation (that presents the dispersion of the data) before job rotation in workstation 1 is 4.63 which is decreased to zero by developing job rotation. This significant decrease guarantees the smoothing and balancing the physical workloads among the operators. On the other side, to demonstrate the efficiency of the proposed model and it's related optimal assignment, we have compared the results of the proposed job rotation with the random rotations. In this way, 10 random job rotations are simulated and the best one is selected to be compared with the proposed rotation. The table 4.7 shows this comparison in detail. The propagation of the different physical workload among the workers and the number of successive high workloads are evaluated to compare these two strategies of job rotation with a fixed job assignment (without rotation).

Proposed optimal job rotation in comparison with the best random rotation

Optimal rotation

Successive As shown in this table, The number of successive high workload (R-R) has been mini-mized by the proposed job rotation model. About the cumulative workload, without job rotation, there are three high workloads (Red) which are followed by another high workload whereas by the best random rotation R-R is occurred one time and by the proposed job rotation model, a Red is never followed by another Red. Moreover, for each one of the ergonomic criteria, the number of R-R workloads is decreased by employing the proposed job rotation without the significant increases of the Y-R and R-Y. The columns of the STDV show the dispersion of the different types of workload on the workers. The results of the optimal rotation show an important decrease on the dispersion of the workload criteria. It guarantees a homogeneous workload being exposed to the workers.

STDV high workload R-R Y-R R-Y* Best random rotation Successive STDV high workload R-R Y-R R-Y Without rotation Successive STDV high workload R-R Y-R R-Y Ergo criteria Repetition 0 1 0 1.19 1 0 1 1.42 3 0 0 2.

4.4/ DISCUSSION

This study presents a job rotation strategy that balances the daily physical workload and avoid the successive high workloads for the operators during a working-day. At the first step of the research, we had to determine how to analyze the jobs, which criteria must be considered and how to obtain the workload level of the jobs in each ergonomic criterion.

There are many various ergonomic criteria which could be considered, but the number of criteria is a critical factor for solving the job rotation mathematical model. That is because the computational time for solving the model depends on the number of considered criteria. Hence, each job was evaluated by twenty sub-criteria which were clustered into five principal criteria. The clustering approach helps us to analyze the jobs by maximum number of criteria and enables us to solve the job rotation mathematical model in a reasonable time. The contribution of this research in comparison with the job rotation model presented by [START_REF] Yoon | A model for developing job rotation schedules that eliminate sequential high workloads and minimize between-worker variability in cumulative daily workloads : Application to automotive assembly lines[END_REF], is the evaluation procedure of the jobs. They have analyzed the physical workload only by the posture, whereas this study has considered various criteria for the physical workload evaluation. On the other hand, the proposed model considers two ergonomic objectives simultaneously. The first one is the daily physical workload to which the operators are exposed where the model aims to balance that among the workers. The second ergonomic factor which is analyzed in our model, is the successive high workloads for a worker. This factor has been also taken into account in the model of [START_REF] Yoon | A model for developing job rotation schedules that eliminate sequential high workloads and minimize between-worker variability in cumulative daily workloads : Application to automotive assembly lines[END_REF] where they paid a special attention to the posture of the different parts of body. But our model minimizes the successive high workloads of different types including posture, repetition... as well as the high cumulative workload. This consideration (avoiding the successive high workloads) has been imposed to the mathematical model by constraints 4.15 and 4.18. Constraint 4.15 signifies that if a worker has a high workload of posture in current period, in the next period he has to be assigned to a job with a low workload of posture. Similarly, constraint 4.18 implies that if a worker has a high cumulative workload, in the next period he has to be assigned to a job with a medium or low cumulative workload. The balancing has been proved by employing Standard Deviation (STDV) which is most common index to evaluate the propagation where the results are shown in table 4.6.

A detailed analysis on the STDV for each one of the ergonomic criterion has been performed and the results are presented in table 4.7.

Another job rotation model for balancing the ergonomic factors in the manufacturing domain has been presented by [START_REF] Otto | Incorporating ergonomic risks into assembly line balancing[END_REF]. The first contribution of our research in comparison with theirs is our procedure of the ergonomic evaluation of the jobs. In this way, we have proposed a mathematical approach to obtain the quantitative scores for the level of the physical workloads of different types. Whereas, they estimated the ergonomic risks of the jobs and they considered the potential risks on the workers in their balancing (job rotation) model. Hence, our considered parameters for developing job rotation model are different from their parameters. In fact, they aimed at smoothing the the ergonomic risks but our objective is to balance the different types of the physical workload together with preventing the successive high workloads on the workers. Another additional consideration which is included in our model is capability of the workers and learning costs. In the case study, the workers had been skilled for the particular workstations. The policy of the company was to not invest additional cost and time for learning the operators. Therefore, in this research a new model of job rotation is programmed in which the rotations occur only inside the workstations.

The advantage of the proposed approach in comparison with the classical job rotation, where the workers can be assigned to all of the jobs, is it's learning cost and time and also the complexity of the manpower planning will be reduced. According to the cumulative workload column of this table, the daily workload scores of the operators are well balanced by this strategy. But there is no consideration about the capability of the workers or the learning aspect (cost and time that the operators need to be skilled and adapted to a job). Note that, the presented mathematical model is programmed by GMPL language and is solved by employing the GUROBI solver. Consequently, the term "computational results" in this study implies the results of the GUROBI solver.

4.5/ CONCLUSION

This chapter presented a specific type of job rotation in which the rotations occur only inside the predefined groups. This strategy needs less cost and time for learning the staffs in comparison with the classical job rotation and balances the physical workloads exposed to the operators of each group. At the first step, an ergonomic analysis was carried out for the jobs and its physical workloads were evaluated by different ergonomic criteria. The workload levels were classified into high, medium and low categories. Afterwards, a mixed integer mathematical model was developed to obtain optimal sequences for the group job rotation by aiming to balance the daily physical workloads on the workers. Furthermore, the constraints of the proposed model prevent the operators to face the successive high workloads.

The proposed approach was applied to plan the workforce scheduling for a truck assembly line. The computational results and its related statistical analysis demonstrate that the workload scores are balanced among the operators. The model is well adaptable for other production and service systems to reduce the risks of the WMSDs and occupational diseases. The proposed job rotation method can be favourable for the systems in which the skills required by different jobs are largely different. Considering the productivity factors into the job rotation model combined with the ergonomic issues may be an interesting axis for the future studies. On the other hand, we can consider uncertainty concerns for the estimation of the workload scores by employing the Fuzzy logic or Statistical approaches.

The analyzing of the learning-forgetting effect and learning costs can be other ways as the further researches. Many various objectives have been targeted in the worker assignment and job rotation problems in the production environment. In the classical worker assignment problems, the economic goals are often one of the most important factors to be considered. For the job rotation problems, the nature of the objectives is different and most of the time the ergonomic goals are targeted. By regarding the importance of the musculoskeletal disorders (MSDs) and the occupational disease, which is progressively increasing, the application of the job rotation approach in the manufacturing is growing. Apart from the ergonomic criteria, the job rotation is used in the worker assignment to face unplanned absenteeism and unavailability of the workers.

MULTI-OBJECTIVE

In this thesis, we present an integration of the worker assignment and job rotation problems as a novel optimization problem in the production domain. A multi-objective mathematical model is proposed for the mentioned problem. Two main objectives of the model are aimed at balancing the physical workload level among the workers and improving the productivity level of the studied assembly line. The mathematical model is applied to a part of a truck assembly line and is solved by using Gurobi solver.

5.1.2/ PROBLEM DESCRIPTION

To develop a worker assignment and job rotation platform in a manufacturing system, the workers and the jobs as the basic components must be precisely analyzed. Many various criteria can be considered in this analysis. Depending on the objective and the considerations of the job rotation model, the workers and the jobs are evaluated by different parameters. In this study two main objectives are targeted for the worker assignment and job rotation model. The first one is to balance the physical workload level that the workers are exposed during a day. This is because the jobs of the studied system have not the same level of load. The physical workload level of different jobs is evaluated by a local standard of the company that gives an integer value between 1, as the minimum and 10, as the maximum workload. In this standard the jobs by a workload level less than or equal to 4 are considered as the low workload jobs. The jobs with a load from 5 to 7 are the medium jobs and the workload level more than or equal to 8 implies a high workload job. As an example, the results of the evaluation of the nine jobs (J1 ... J9) are shown in the table 5.1.

Physical Workload Evaluation of the Jobs

J1 J2 J3 J4 J5 J6 J7 J8 J9 Workload Amount (L) 7 6 7 10 2 8 9 2 6 Workload Level M M M H L H H L M Binary Parameters U 0 0 0 0 1 0 0 1 0 V 1 1 1 0 0 0 0 0 1 W 0 0 0 1 0 1 1 0 0 TABLE 5.1 -Physical Workload Evaluation of the Jobs
In this table H, M, L signify respectively the High, Medium and Low physical workload level and the the binary parameters are defined to ease the modelization of workload mathematically.

The second objective of the presented worker assignment problem is to minimize the production cycle time of the studied manufacturing system. In this way, the efficiency and also the capability of the workers are evaluated because the workers are heterogeneous.

For the efficiency, the operating time of the workers on different jobs is considered. In this part we have made a test on the operators to obtain their operating time on different jobs.

The result of the mentioned test for nine operators (I1 ... I9) on the nine jobs (J1 ... J9) is shown in the table 5.2. Note that the actual production cycle time of the studied system is 5 minutes. It means that every worker must complete his job before five minutes.

Workers' Operating Time J1 J2 J3 J4 J5 J6 J7 J8 J9 I1 3. The other consideration of the proposed job rotation model is the capability of the workers.

Actually, the problem concerns the mono-skilled and multi-skilled workers. The capability of the workers is evaluated for working to different workstations. The result of this analysis is shown in the table 5.3 by "Y" and "N" that imply respectively "YES" and "NO".

Workers' Capability

WS1 WS2 WS3 WS4 I1 Y Y N N I2 N Y N Y I3 Y Y N Y I4 Y N Y N I5 N N Y Y I6 Y Y Y Y I7 N N Y N I8 N Y Y Y I9 Y N N Y TABLE 5.3 -Workers' Capability
As an example, worker number six (I6) is a multi-skilled worker who is able to work in all workstations whereas worker number seven (I7) is a mono-skilled worker who can work only in workstation three (WS 3). In this research, we present a novel worker assignment and job rotation problem that incorporate various considerations simultaneously. The heterogeneous workers, capability and the efficiency of the workers, together with the ergonomic criteria and the dissimilarity of the workload of the jobs are the main considerations of this problem. A multi-objective mathematical model is proposed for the problem which is presented in the next section.

5.2/ MULTI-OBJECTIVE PROGRAMMING FOR JOB ROTATION SCHE-DULING

The studied problem is modeled mathematically by employing a multi-objective mixedinteger programming approach. Firstly, the elements of the mathematical model as the parameters, variables and indices are presented. The formulation of the problem which is composed of three objective functions and various constraints is introduced afterwards.

5.2.1/ INDICES, PARAMETERS, AND VARIABLES

A mathematical model has one or multiple dimensions and each one is presented by an index. The proposed model contains five dimensions as worker (i), job ( j), workstation (k), period (p) and day (d). The parameters and the variables of the model are introduced by employing these indices.

The parameters of the model are the constant exogenous variables which are imposed to the model as the data. The parameters of the proposed model are as follows.

m : Number of available workers to be assigned to the jobs.

n : Number of considered jobs in the production system.

r : Number of working periods per day.

t : Number of working days in the planning horizon.

A i j : Binary parameters for presenting the capability of the workers, where A i j = 1, if worker i is able to work in the job j and A i j = 0, otherwise.

U j , V j , W j : Binary parameters for presenting the workload level of the jobs, and signify respectively the low, medium and high workload level. As an example, U j = 1, if the workload level of the job j is low and U j = 0, otherwise.

L j : Integer parameters that present the quantitative workload amount (from 1 to 10) of job j. It signifies that if a worker is assigned to job j for a period of a day, he is exposed to a physical workload amount of L j .

OP i j : Operation time of job j if it is done by worker i.

ε : Maximum authorized difference between total workloads that different operators are exposed.

The variables of the model are obtained by solving the model and they determine the state of the system. For solving a model, the decision variables are computed such that the objective of the model is optimized. The other variables (state variables) are computed from the decision variables and parameters of the model. The variables of the proposed job rotation model are as follows.

X i jpd (Decision variables) : Binary variables where, X i jpd = 1 if worker i is assigned to job j in the period p of day d, and X i jpd = 0 otherwise.

DL id : Daily workload that the worker i is exposed during the day d.

T L i : Total workload that the worker i is exposed during the planning horizon.

PT kpd : Production time of workstation k in period p of day d .

CT pd : Production cycle time in the period p of day d .

5.2.2/ OBJECTIVE FUNCTIONS

Three mini-max objectives are considered in the formulation of the problem which are presented as follows.

Objective 1 (Daily Workload) :

Minimize Z 1 = MAX i∈I, d∈D {DL id } (5.1)
Objective 2 (Cycle Time) :

Minimize Z 2 = MAX p∈P, d∈D CT pd (5.2)
Objective 3 (Total Workload) :

Minimize Z 3 = MAX i∈I {T L i } (5.
3)

The first one (Z 1 ) signifies the minimization of the maximum workload that the workers are exposed during a day. This objective results in the balancing of the daily workload among the workers. In the second objective (Z 2 ), the production cycle time is targeted to be minimized. In fact, by employing job rotation approach, the production time varies from one period to another because of the efficiency of the workers. In a period (p) of a day (d), the production cycle time (CT pd ) is equal to maximum operating time of the workers. Hence, a mini-max formulation is proposed to minimize the maximum cycle time of the different periods of the planning horizon. The third objective (Z 3 ) is aimed at levelling the total workload to which each worker is exposed during the planning horizon. This objective is also formulated by a mini-max equation that is to minimize the maximum total workload on a worker.

5.2.3/ CONSTRAINTS AND REQUIRED CALCULATIONS

This study concerns a combinatorial optimization problem that is composed of various constraints of diverse domains. These constraints are separately presented as follows.

5.2.3.1/ ASSIGNMENT CONSTRAINTS

m i=1 x i jpd = 1 ∀ j ∈ J, p ∈ P, d ∈ D (5.4) n j=1 x i jpd = 1 ∀ i ∈ I, p ∈ P, d ∈ D (5.5) n j=1 x i jpd = n j=1 x i j(p+1)d ∀ i ∈ I, p ∈ P -, d ∈ D (5.6) t d=1 r p=1 n j=1 x i jpd = t × r ∀ i ∈ I (5.7)
The first and second sets of the constraints (5.4, 5.5) are the classical constraints of the assignment problem. They guarantee respectively that a job in each period of a day is done by one and only one operator and a worker during a period is assigned to one and only one job. The third set of constraints (5.6) signifies that if a worker works in a period of a day he must also work on other periods of this day. It means that the workers have to work whole the day not only one or two periods. The constraints (5.7) signify the total number of periods in which one worker has to work and ensure that they are assigned to the jobs all of the periods every day. x i jp(d+1) ∀ k ∈ K, i ∈ I, p ∈ P, d ∈ D - (5.9)

x i jpd ≤ A i j ∀ i ∈ I, j ∈ J, p ∈ P, d ∈ D (5.10)
Two sets of the constraints (5.8 and 5.9) are about the special conditions of the job rotation in the considered problem. As mentioned in the problem description part, the job rotation in the studied system is just inside of the workstations. It means that the workers can be assigned to only the jobs which are in the same workstation. According to these equations, if a worker is assigned to the workstation k in the period p, in the next periods and next days he has to work in this workstation. The constraints (5.10) guarantee that a worker can be assigned to only the jobs in which he is skilled. It is assumed that if a worker is able to work in a workstation, he is capable to do all of the jobs in this workstation.

5.2.3.3/ ERGONOMIC CONSTRAINTS

n j=1 x i jpd × W j ≤ n j=1 x i j(p+1)d × (U j + V j ) ∀ i ∈ I, p ∈ P -, d ∈ D (5.11) n j=1 (x i jpd + x i j(p+1)d ) × (W j + V j ) ≤ n j=1 x i j(p+2)d × 2 × U j ∀ i ∈ I, p ∈ P -{r, r -1} , d ∈ D
(5.12)

DL id = r p=1 n j=1 x i jpd × L j ∀ i ∈ I, d ∈ D (5.13) T L i = t d=1 DL id ∀ i ∈ I (5.14) T L i -T L f ≤ ε ∀ i, f ∈ I (5.15)
The equations (5.11, 5.12) present the ergonomic constraints that are considered in the proposed job rotation implementation. The first set (5.11) ensures that if a worker has a high workload job in a period, he must be assigned to a medium or low workload job in the next period. This constraint prevents two successive high workload jobs for a worker during a day. The constraints (5.12) are similar to the previous ones and signify that if a worker is assigned to a high and medium workload job in two successive periods, in the next period he must be assigned to a low workload job. In the studied system this constraint is a optional (soft) one and it can be employed where it is feasible. The equation (5.13) is to calculate the daily workload to which each worker is exposed. The daily workload is determined by the sum of the workloads related to each period during the day. The total workload that the workers are exposed during the planning horizon is obtained by the sum of the daily workloads as presented in equation (5.14). Another ergonomic constraint is imposed to the model by the equation ( 5.15) and it guarantees balancing of total workload on the workers. Note that, the third objective function Z 3 (5.3) can be replaced with this constraint by employing "epsilon method" to solve our multiobjective mathematical model. This method is applied for the studied system as explained in the next section. (5.16)

5.2.3.4/ MAKESPAN CALCULATIONS

PT kpd = MAX i∈I, j∈WS k OP i j × x i jpd ∀ k ∈ K, p ∈ P, d ∈ D
CT pd = MAX k∈K PT kpd ∀ p ∈ P, d ∈ D (5.17)
As mentioned before, the production time of a workstation is calculated by maximum operation times of the jobs which are carried out in the workstation. The operating time of a job is depended on the efficiency of the operator (OP i j ). Because of the job rotation, the processing times of the workstations vary from a period to another. Hence, each workstation has a particular processing time every period. The processing times of the workstations in different periods are calculated by equation 5.16. In this study, a production cycle time is determined for each working period. It is obtained from the maximum workstation's processing times during the period as formulated mathematically in equation 5.17. The presented mathematical model is employed to optimize a part of a production system which is explained in the next section.

5.3/ NUMERICAL APPLICATION AND COMPUTATIONAL RESULTS

The multi-objective model which was presented in the previous section is used for the implementation of job rotation in a truck assembly line. In fact, the mathematical model helps us to obtain an optimal job rotation in the workstation of this manufacturing system. As mentioned in the problem description part, the considered system composed of four workstations of production line. The workstations contain one or multiple jobs and each job needs a permanent operator. Hence, a workstation needs one or multiple operators. In the studied system, four considered workstations are composed respectively of four, five, five and four jobs. The multi-objective model which is proposed to this system is aimed at assigning the heterogeneous workers to the jobs such that the production time is reduced and the workload is balanced on the workers. Because of the ergonomic constraints, we have considered the possibility of the job rotation among the workers. For that, the capability of the workers is determined by a table that indicates all of the jobs that each worker is able to do. In the studied company, the daily working time is eight hours and the workers have a pause between each two hours. Therefore, there are four working periods per day and there is a possibility of job rotation during the breaks between working periods.

To obtain the optimum worker assignment and job rotation, the mathematical model is solved by following three different scenarios. At first, only the first objective (Smoothing the daily workload) is considered and model is solved as a mono-objective. The results of this scenario for the nine first operators (I1 -I9) during the first day (D1) are shown in table 5.4. As shown in this table, as an example, the operator number one (I1) in the first period (P1) is assigned to the job number five (J5), after the first break he is assigned to job number seven (J7), then he works in job number five in the third period and finally he is assigned to job number six in the last working period (P4) of the first day (D1). The daily workload for each worker is calculated by the sum of the workloads of the jobs which is done by the worker in different periods. For the first operator (I1), the daily workload (DL) is calculated by DL(I1) = L 5 + L 7 + L 5 + L 6 = 2 + 9 + 2 + 8 = 21 (According to the table 5.1 in the section 5.1.2. The objective of this scenario is only to minimize the maximum "daily workload" on the operators without considering the worker's efficiency and production time. As a result, the operator number nine (I9) is exposed to the maximum workload amount of 30. It can be seen that the operating time and production cycle time are not considered and they are not optimized. The production cycle time by using this strategy is 5 minutes which is not a agreeable solution.

Worker Assignment and Job Rotation based on the Workload Levels

Day Period I1 I2 I3 I4 I5 I6 I7 I8 I9 D1 P1 J5 J16 J15 J11 J17 J12 J10 J9 J3 P2 J7 J15 J17 J13 J18 J12 J14 J6 J2 P3 J5 J16 J18 J13 J17 J12 J10 J9 J3 P4 J6 J15 J16 J12 J18 J10 J11
In the second scenario, the model is solved by only the second objective (Minimization of the production cycle time). The results of applying this strategy for two workstations containing nine jobs, during the first day are shown in table 5.5. Time 3.5 4.2 3.8 4 This table shows the sequence of the workers which are assigned to each job in different periods of the day. The assignment of the jobs to the workers is based on the efficiency of the workers by regarding to the operating time table which was presented in the section 2 (table 5.2). There are the jobs that the best operator repeats that every period by respecting the ergonomic restrictions. For instance, job number one (J1) is done by operator number eighteen (I18) in all of the periods of the day. But most of the time, because of the ergonomic constraints in the model, the best operator of each job can not repeat that every period. According to the table, for each one of the jobs the processing time is obtained from the maximum operating time of the operators who work in the job in different periods. The workstation processing time is calculated by the maximum processing time of the jobs which are done in the workstation. Finally, the cycle time is obtained from the maximum processing time of the workstations. The optimum cycle time obtained by solving the job rotation model is 4.3 minutes which is the best possible solution from the point of view of productivity. This approach does not consider the smoothing of the workloads among the operators. The maximum daily workload is on the operator number one (I1) with an amount of 32 which is higher than the first strategy.

Assignment and Job Rotation based on the Operating Times

Day Period J1 J2 J3 J4 J5 J6 J7 J8 J9 D1 P1 I18 I9 I3 I1 I13 I11 I8 I2 I14 P2 I18 I1 I3 I9 I8 I2 I13 I11 I14 P3 I18 I9 I3 I1 I13 I11 I8 I2 I14 P4 I18 I1 I3 I9 I14 I13 I2 I11 I8 MAX Processing
In the third scenario, we consider all of the three objectives which are presented in the model formulation section. Two approaches, as Epsilon-Constraint and Linear Aggregation, are employed simultaneously to solve the proposed multi-objective model. In this way, the first and second objectives (Daily workload and Cmax) are normalized and then a weighted sum method is used to transfer to a mono-objective model. The third objective function is convert to a constraint by using the Epsilon-Constraint method as presented in the equation 5.15. The results of applying this strategy are shown in table 5.6. The adapted mono-objective model is solved by employing different weights for the objectives. As shown in the column of "solution state", four different solutions are obtained. Among these solutions, two of them are non-dominated (number 1 and number 2) and two others (number 3 and number 4) are dominated by solution 2.

Multi-Objective Analysis (Linear aggregation)

One of the non-dominated solutions is the same as we have obtained by using strategy 2 (table 5.5 ). It can be seen that the solution obtained by strategy 1 (table 5.4) is dominated by the solution 2. With regard to the objective values of the solution 2, it can be concluded that the proposed multi-objective approach optimize the "daily workload (Z1)" and results in an agreeable value for the "production time (Z2)".

Note that, the proposed mathematical model has been programmed by employing GMLP mathematical programming language and has been solved applying branch and bound algorithm using GUROBI solver.

5.4/ CONCLUSION

In this chapter, a job rotation platform for a manufacturing system has been implemented. The integration of the worker assignment and the job rotation problems by considering the heterogeneous workers, different task execution times for the workers, capability of the workers and different workload levels of the jobs consist a novel combinatorial optimization problem in the production domain. the production cycle time as the productivity and the daily workload as the ergonomic criteria have been targeted in the presented problem.

By solving the mathematical model of the job rotation, the optimum worker sequence for the jobs is obtained. Different scenario, according to the decision maker or user point of view, can be defined for this problem and for each scenario one or more optimum solution is calculated. The numerical application illustrated the adequacy of the proposed mathematical model. For the future, proposing a heuristic or meta-heuristic algorithm for this problem can be a interesting way as the future research.

SGAP FORMULATION FOR WORKFORCE SCHEDULING

6.1/ INTRODUCTION

Human resource planning in a production system could be considered as a specific version of the Assignment Problem (AP). This part of our research deals with the weekly worker assignment to the workstations/jobs in an assembly system which is modeled as a sequencing assignment problem. The term sequencing assignment problem in the present study could be interpreted to mean a number of the classical assignments that occur sequentially. Each assignment belongs to a period of time and depends on the previous ones. Hence, the parameters of the problem must be synchronized after determining an assignment.

The study aims at obtaining the optimal assignment of the appropriate operators to the workstations. The considered assembly line consists of the workstations which are in series (flowshop system) and each workstation is composed of several jobs. In a workstation, as there are no precedence relationships between jobs, they can be processed in parallel. Consequently, several workers are assigned to the same workstation. Therefore, the studied problem can be regarded as a special type of the generalized assignment problem (GAP) which is a combinatorial optimization problem.

The problem contains the heterogeneous workers with different capacities and a planning period of one week. The restriction of working-days and off-days on the workers is also considered in this research. The production system works everyday and the workers have five working-days and two off-days per week. Therefore, seven worker assignments (one per day) are needed for this system and the objective is to minimize the production time by assigning the efficient workers to the jobs such that the number of working-days is respected for every workers. In the studied assembly line, the workers are able to do all of the jobs but their skills are different. The objective is to select the most efficient worker for each job. The daily assignments are correlated because of working-day/offday restriction. Hence, a sequencing generalized assignment formulation is applied to model this problem mathematically by using mixed-integer programming (MIP).

The term Sequencing Generalized Assignment Problem (SGAP) was presented for the first time by [START_REF] Moussavi | Productivity improvement through a sequencing generalised assignment in an assembly line system[END_REF] as multiple generalized assignments which must be carried out one after the other. This problem is explained in detail in next sections. 59 6.1.1/ GENERALIZED ASSIGNMENT PROBLEM (GAP)

The production system which was presented in the previous section, can be considered as a GAP because each workstation is composed of one or more workplaces in which one and only one worker must be assigned to a workplace in each day. To adapt this problem to GAP, the workers can be viewed as the agents and the workstations can be viewed as the jobs. Note that the maximum number of working-day for each worker is viewed as the capacity of the agents.

The classical GAP concerns the assignment of n jobs to m agents such that each job is assigned to exactly one agent by respecting the capacity of the agents [START_REF] Ross | A branch and bound algorithm for the generalized assignment problem[END_REF]. The decision variables x i j represent the assignment of agent i to job j, with c i j the cost of assigning job j to agent i, a i j the resource used by job j assigned to agent i and b i the capacity of agent i.

Minimize Z(x) = m i=1 n j=1 c i j x i j (6.1)
S ub ject to :

n j=1 a i j x i j ≤ b i ; ∀ i = 1, ..., m; (6.2) m i=1
x i j = 1; ∀ j = 1, ..., n; (6.3)

x i j = 0 or 1; ∀ i = 1, ..., m; j = 1, ..., n; (6.4)

Many researchers have proposed different exact and approximated methods to solve the generalized assignment problems in different scales.

On the other hand, in the literature, there exist various extensions for the GAP with divers solution methods. In this part, at first, the solution methods which existed in the earlier works for the classical GAP are presented. Afterwards, different extensions of the GAP and their related solving methods are announced.

6.1.2/ DEFINITION OF THE SEQUENCING GENERALIZED ASSIGNMENT PROBLEM (SGAP)

In this study, the worker assignment is modeled by using GAP formulation. The objective is to maximize the productivity by scheduling the workforce and with the consideration of the availability of the workers and the possibility of job rotation. To take into account the planning horizon and availability of the workers, we present an extended variant of the GAP in which there exists an additional dimension as the periods other than the classical GAP dimensions (agents and jobs). In fact, the term Sequencing Generalized Assignment Problem (SGAP), is introduced in this thesis as follows :

Definition 1 : Sequencing Generalized Assignment Problem (SGAP)

An extended variant of the assignment problem consisting of multiple GAPs that occur consecutively, whilst ensuring the number of working-days and off-days for each agent are respected.

Figure 6.1 shows an simple example for SGAP containing three workers, and six jobs. The capacity of the agents is three jobs per day (Generalized aspect), for a planning horizon of three days involving two working-days and one off-day for each worker (Sequencing aspect).

FIGURE 6.1 -Sequencing Generalized Assignment Problem

The SGAP is modeled by using an integer linear programming as follows : x i jp = 1; ∀ j = 1, ..., n; p = 1, ..., l (6.8)

Minimize Z(x) =
x i jp = 0 or 1; ∀ i = 1, ..., m; j = 1, ..., n; p = 1, ..., l (6.9)

Where d j represents the maximum number of authorized working-days during the planning horizon for each worker, and x i jp the binary decision variable represents whether worker j is assigned to workstation i in the period (day) p or not.

6.2/ PROBLEM DESCRIPTION

This study concerns the workers' assignment to manufacturing stations in an assembly line in order to minimize the production time. The considered assembly line consists of the serial workstations. A workstation in this system contains diverse workplaces which must be performed simultaneously. The workers are assigned to the workplaces.

The problem concerns the heterogeneous workers with different skill level. The task executing time in the workplaces depend on the workers' skill level. It means one individual may be very efficient in a workplace whereas he is not able to complete another workplace in a given period. It is assumed that all the operators are able to work in all the workplaces, only the efficiency level is different. The problem is assigning workers to the workplaces in order to minimize the production time where the task execution time must not exceed the production cycle time. The production time is the sum of the processing time of the serial workstations. The workstation processing time is calculated by maximum operating time of the operators who works in different workplaces of the workstation concurrently. For minimizing the workstation time, we must reduce the maximum workplaces execution time. Hence, the worker allocation model should consider not only the best operator for each workplace but also balancing the operating times in a workstation. Figure (6.2) shows the considered problem consisting of the tasks in parallel and the workstations in series.

In this study the term "task" implies the workplace which is placed in a workstation. Note that the task execution times are not the fixed values and they vary as a function of the workers' efficiency. According to the figure, a j and b j signify respectively the best and worst execution time of task j.

The generalized assignment problem can be adapted to the studied problem in which a worker is assigned to one and only one workstation in each period such that all the workplaces of the workstations should be fulfilled. This problem must be solved over a planning horizon composed of the several periods thus, the SGAP structure is adapted to FIGURE 6.2 -Generalized assignment for the assembly line model and optimize the studied system. The SGAP comes from the difference between the length of planning horizon and the maximum number of working-days for each worker. Therefore it is not possible to repeat the best assignment for all of the periods because of the availability of the workers.

The studied assignment problem as the daily allocation of human resources is performed by aiming to reduce the production time. On the other side, the considered production system works seven days a week whereas the operators work five days. Thus the number of available operators is more than the tasks because in each day certain operators are in working-day and others are in off-day. As a result, the employment of the best daily allocation for the following days is not possible. Note that, the manpower planning horizon is one week. In fact, we deal with the sequencing assignments in which each assignment is a generalized one and we need to connect the individual assignments. As regards the objective of the studied problem which is minimizing the maximum task executing time, we deal with a sequences of the Bottleneck Generalized Assignment Problem (BGAP) [START_REF] Cattrysse | A survey of algorithms for the generalized assignment problem[END_REF] On the other hand, the input of the presented optimization problem, as the assignment matrix, is the efficiency (task executing time) of the workers in different workplaces. In fact, the worker allocation is performed based on the assignment matrix. The elements of the assignment matrix in this study are the operating time of the workers in different tasks. The operating times are depended on the efficiency of the worker on the task. Note that, the efficiency of the workers in different tasks are not identical. Thus, to obtain the assignment matrix we have to calculate the efficiency of the operators. Note that, in this research we use the procedure of the efficiency calculation presented by [START_REF] Moussavi | Reducing production cycle time by ergonomic workforce scheduling[END_REF] . After that, by employing the assignment matrix, optimization problem can be solved. For solving this problem by the aim of obtaining the optimum workforce schedule, a mixed integer mathematical model is presented. With reference to the structure and the objective of the problem, this model is based on the Sequencing Bottleneck Generalized Assignment Problem (SBGAP). The objective of the allocation model is to minimize the production time in order to improve the productivity (number of product per day). The model is presented in detailed in next sections.

6.3/ PRIMAL MATHEMATICAL MODELALIZATION BASED ON THE SGAP

The mathematical model consists of the objective function which must be optimized and the constraints which should be respected. The equations of these two parts composed of the parameters which are unchangeable along the problem and the variables which must be calculated by solving the model in order to optimize the objective. The model and its relevant elements are presented as follows.

6.3.1/ PARAMETERS

The parameters are the predefined data which must be specified for solving the model. The parameters of the presented model are as the following :

N ws : Number of workstations considered for the worker assignment ; WD S : Number of working days of the production system during the planning horizon ;

6.3.2/ VARIABLES

The variables are the fundamental elements of a mathematical model and they are determined by solving the model so that the objective function become optimized. The variables of the presented model are as follows.

X p i j : Binary variable where X p i j = 1 if worker i is assigned to task j in period p ; and X The objective of the model is what we aim to optimize. In the studied problem the objective is a minimax one over a sequence of periods thus, the problem concerns a Sequencing Bottleneck Assignment which is defined as :

Minimize Z = N p p=1 N ws k=1 MAX j∈WS k , i∈I {X p i j ×t i j } (6.10)
The objective formula signifies the sum of the production times of all of the planning periods where MAX j∈WS k , i∈I X p i j * t i j implies the processing time of the workstation k, in period p (maximum executing time of all of the operators who work in this workstation in the considered period). The sum of the processing times of the workstations is the production time for the considered period. Accordingly N ws k=1 MAX j∈WS k , i∈I X p i j * t i j signifies the production time in period p. Finally, the sum of the production times of all periods is the objective of the studied problem by aiming to minimize that.

CONSTRAINTS

The sequencing assignment problem, which is studied in this research, consists of two types of the constraints. The first set of the constraints implies the assignment restrictions and the second set defines the scheduling and process constraints. The assignment constraints of the proposed model demonstrate two extensions of the classical assignment problem as the generalized and the sequencing (multiple) which has been considered in the modelization of the studied problem. In fact, these constraints determine the structure of the assignment problem and are defined as follows.

N p p=1 m j=1 X i jp = WD I ∀ i ∈ I (6.11) m j=1 X i jp ≤ 1 ∀ i ∈ I, p ∈ P (6.12) n i=1 X i jp = 1 ∀ j ∈ J, p ∈ P (6.13) n i=1 j∈WS k X i jp = M k ∀ k ∈ K, p ∈ P (6.14)
The fist set of the constraints (6.11) ensure the predefined number of working days during the planning horizon for each worker. These constraints imply the sequencing structure of the considered assignment problem.

The second and third sets (6.12,6.13) are the classical constraints of the assignment problem and signify respectively that a worker is not assigned to more than one task in a period, and each task in each period is performed by one and only one worker. The forth set of the constraints (6.14) adapts a special version of the generalized assignment for the studied problem. Note that, This set of constraints in the classical assignment problem are as the inequalities (lower or equal) whereas the considered problem which are as the equalities that is why we announced a special version of the GAP. In the presented model, these constraints guarantee the assigning of a certain number of workers to each workstation. As explained in the previous parts, a workstation is composed of a certain number of tasks. By assigning one worker to each task, in fact, multiple workers are assigned to a workstation. The number of tasks (workers requirement) in each workstation is defined by the problem (M k ).

Apart from the assignment constraints, the studied problem concerns the production and scheduling constraints which are related to the researched system. This disaggregation of the constraints enable us to easily apply the presented assignment model to divers systems. In the studied production system, the workstations take place in series. As a result the problem concerns the priority and scheduling considerations and their related constraints which are presented below. (6.16)

S p 1 = 0 and F p k-1 ≤ S p k ∀ k ∈ K, k ≥ 2, p ∈ P (6.15) F p k = S p k + MAX j∈WS k {t i j X i jp } ∀ k ∈ K, p ∈ P
t i j = E i j * (T max j -T min j ) ∀ i ∈ I, j ∈ J (6.17) PT p = F k=N ws ∀ p ∈ P (6.18)
The first set of the process constraints (6.15) ensures the priority of the workstations, because they are in series and the execution of each workstation can be started once the previous workstation is completed. The second set (6.16) defines the relationship between starting, ending and processing times in each workstations. The constraints (6.17) calculated the executing time of the workers in different tasks as a function of the efficiency of the worker in the task. The processing time of the workstation is defined as the maximum task execution time of all of the workers who work in considered workstation concurrently (MAX j∈WS k {t i j X i jp }). Finally, the last set of the constraints (6.18) determines the production time for each period.

The mathematical model above, presents an extended version of the assignment problem in a production system. The structure of the system persuades us to adapt our model to the generalized assignment problem. The planning period of the considered assignment, which is one week, pushed us to present an extension of the GAP by considering a sequence of the GAPs which occur one after another. As mentioned before, this extension has been named Sequencing Generalized Assignment Problem (SGAP). The studied SGAP is solved by three solving approaches which are attentively explained in the next sections.

As indicated in various earlier works, GAP is a well-known NP-hard combinatorial optimization problem. Consequently, the SGAP which is an extension of the GAP with one more dimension and additional constraints, will be an NP-hard. Therefore, solving the medium and large sized SGAP by any exact solver needs a huge computational efforts.

In this part, as the first solving method, the presented SGAP model is solved by an exact algorithm employing Gurobi as a mixed integer solver. The computational efforts needed to solve SGAP persuade us to apply the approximation approaches. Hence, two matheuristic approaches and a hybrid heuristic approach are presented to solve such problems.

The proposed algorithms reduce significantly the computational time and the obtained solutions have very slight deviations from the optimal solutions.

6.4/ IMPROVED MATHEMATICAL MODEL

The proposed mathematical model in the previous section, is improved by more organizational issues and more considerations. For instance, an upper bound and a lower bound are defined as the parameters for the number of working-days for each operator. Furthermore, the decision making in the previous model was based on the efficiency of the workers, whereas in the improved model is based on an assignment matrix (Y i j ) that presents the operating time of each worker on each job. The model is presented as follows.

6.4.1/ PARAMETERS

UD : Upper bound on the number of working-days during the planning.

LD : Lower bound on the number of working-days.

(WS k = { j ∈ J | k-1 l=0 N l < j ≤ k l=0
N l : where N 0 = 0}).

6.4.2/ VARIABLES

In the model, there is a set of decision variables named X i jp and some other variables as :

X i jp : Binary, where X i jp = 1 if operator i is assigned to job j in period p, and X i jp = 0 otherwise.

S kp , PT kp , F kp : They present respectively the starting, processing and ending time of workstation k in period p.

W ikp : Working time of worker i in workstation k in period p. Where W ikp = Y i j if worker i is assigned to job j in the period p and job j is in workstation k ; W ikp = 0 otherwise.

CMAX p : Production time (for producing one product) in period p.

Z : Average of the production times.

The mixed-integer mathematical model which is presented in this study, contains a minimization objective function together with two different kinds of constraints as the assignment and the scheduling constraints.

6.4.3/ OBJECTIVE FUNCTION

The model is aimed to minimize the average of the production time on the planning periods and defined as the following :

Minimize Z = t p=1
CMAX p /t; (6.19)

6.4.4/ ASSIGNMENT CONSTRAINTS

The first set of constraints is the classical assignment constraint and implies that each job in each period is fulfilled by one and only one operator.

m i=1 X i jp = 1 ∀ j ∈ J, p ∈ P; (6.20)
The second set of constraints implies that each worker during a day can not be assigned to more than one job. Thus the worker has whether one job (if he is in his working-day) or without the job (if he is in his off-day). This condition is defined as follows :

n j=1 X i jp ≤ 1 ∀ i ∈ I, p ∈ P; (6.21)
The maximum and minimum number of working-days (for each operator during the planning horizon) which are considered in this study as the predefined conditions in the work-force scheduling. These assumptions are imposed on the model by the following sets of the constraints :

l p=1 n j=1 X i jp ≤ UD ∀ i ∈ I; (6.22) l p=1 n j=1 X i jp ≥ LD ∀ i ∈ I; (6.23) 6.4.5/ SCHEDULING CONSTRAINTS
The scheduling constraints of the model contain the precedence of the production operations and the procedure of the production time calculation. The first set of the scheduling constraints presents the working time of the operators during a production cycle.

W ikp = j∈WS k X i jp * Y i j ∀ i ∈ I, k ∈ K, p ∈ P; (6.24)
These constraints imply the working time of worker i if he is assigned to workstation k in period p ; Note that the W ikp will be zero if worker i is not assigned to the jobs of workstation k in period p. The second set of the scheduling constraints signify the processing time of each workstation in each day. While there is more than one operator working in a workstation, the processing time of the workstation is the maximum working time of the operators. This assumption is modeled as the following :

PT kp = MAX i∈I, j∈k W ikd ∀ k ∈ K, p ∈ P; (6.25)
The constraint is linearized as :

PT kp ≥ W ikd ∀ i ∈ I, k ∈ K, p ∈ P
The next set of the constraints is the classical formula for the precedence of the operations in a serial system like a production line. In this study, the workstations are in series and each one can be started once the last one would be finished and the first workstation is started at T = 0.

S k = F k-1 ∀ k ≥ 2 where S 1 = 0; (6.26)
Finally, the last constraint of this model presents the makespan or total production time for producing one product that is the ending time of the last workstation. The makespan varies from a period to another because the assignments are not the same for all the periods.

CMAX p = PT kp ∀ p ∈ P where k = s; (6.27)

The above constraints were formulated mathematically based on the generalized assignment problem. Moreover, some production and scheduling restrictions were imposed to the problem formulation as the additional constraints.

6.5/ CONCLUSION

In this chapter, the human resource planning in an assembly line system was formulated as a specific variant of the assignment problem. In this way, the sequencing generalized assignment problem was defined and the workforce scheduling in the studied system was modelized mathematically based on the formulation of this new problem. Hence, two mathematical models based on the mixed-integer programming were proposed. The model which was presented in the first step, was improved and well organized in the second step as a contribution of the GAP model.

The objective of the models were to minimize the average of the production times (makespans) on the planning horizon. These models are applicable on various types of the production systems as the parallel, serial and combinatorial systems. Considering the lots of the constraints, the presented problem is NP-hard and the exact methods are not able to solve its related MIP model for the large scales. In the next chapter, we propose an hybrid heuristic algorithm which is able to solve the considered assignment problem in a few seconds with a very slight deviation from the optimum solution. Moreover, two matheuristic approaches are proposed for the studied problem.

SOLUTION METHODS FOR SGAP

The proposed model in the previous section is a mixed-integer mathematical model. At first, this model is solved by employing an exact approach using Gurobi solver. This approach is evaluated by considering instances of different size. However, Gurobi is only able to solve small size instances. The considered problem is a generalization of the generalized assignment problem (GAP) which is known to be NP-hard. Therefore, the sequencing generalized assignment problem is also NP-hard. For solving medium and large size instances of the mentioned problem, three other solving methods are presented in the next sections : a two-phase matheuristic, a matheuristic based on the sequencing assignment approach, and a hybrid heuristic algorithm, which are explained in detail in the next sections.

7.1/ TWO-PHASES MATHEURISTIC APPROACH

In this part, a solving method for SGAP is proposed which is composed of two steps. The aim of the first step is the assignment of the workers to the tasks for the whole planning horizon using a linear transportation model. The first phase produces only the number of periods in which worker i is assigned to task j. However, the exact periods of assignment are not determined. These results and the data feed the second phase during which the exact periods of assignment of workers to tasks are determined in order to optimize the objective function (see Figure 7.1).

The details of this method are presented in the next parts.

7.1.1/ FIRST STEP BASED ON THE TRANSPORTATION MODEL

A linear transportation model is used to solve an essential part of the main problem : the number of periods of assignment for each worker to each task. In this transportation model, workers are regarded as resources and tasks as clients. As mentioned before, the production system works during all days of the horizon, whereas the workers do not : they have working days and off-days. Thus, in the transportation model, the supply of resources (workers) signifies the number of the working days ; and the demand of the clients (tasks) corresponds to the number of planning days. Hence, a classical linear model is presented as follows.

-Parameters : 71 FIGURE 7.1 -Two phases matheuristic approach -S D : The number of days that production system (the tasks) must work ; -WD i : The number of days that worker i is authorized to work in the planning horizon ; -Variable :

np i j : The number of periods that worker i works in task j ;

Minimize U = n i=1 m j=1 t i j ×np i j (7.1) n i=1 np i j = S D ∀ j ∈ J (7.2) m j=1 np i j = WD i ∀i ∈ I (7.3)
This is a classical linear transportation model, which can be easily solved by any linear programming software like Gurobi. The output of this model is the number of periods in which each worker works on different tasks. This output will be the input for the next step to determine that in which days they are assigned to different tasks by considering the objective of the main problem.

7.1.2/ SECOND STEP BASED ON THE SCHEDULING MODEL

After solving the first step, we can remove some constraints of the main problem that are complex to consider, and replace them by a parameter np i j . The main model (as explained in section 6.3) is thus simplified and can be easily solved. According to the primal main model, two constraints 6.11 and 6.12 are replaced by : FIGURE 7.2 -Sequencing assignment for multi-period generalized assignment problem

N p p=1 X p i j = np i j ∀i ∈ I, j ∈ J (7.4)
In fact, the mathematical model of the second step (objective function and constraints) is the same as the main problem with the only modification as explained above. By these changes, the computational time for solving the problem is extremely reduced. In the numerical application part, the computational time and the objective function of this method is compared with the exact method and also an other methods which is explained in the next section.

7.2/ SEQUENCING MATHEURISTIC APPROACH : PRESENTATION OF THE SEQUENCING ASSIGNMENT

In this section, the second matheuristic approach for the sequencing generalized assignment problem is presented This approach is based on the decomposition of the formulation into several classical GAPs. Actually, there are three essential factors that complicate the main model of the problem : the "worker", the "task" and the "period". To simplify the main model of the SGAP, an approach is proposed in which the period's dimension p is removed. As a result, an assignment for the first period is obtained for all workers. After this step, the parameters are modified and the number of working days for the assigned workers is reduced by one. In fact, the number of working days in this approach is regarded as the availability of the workers. The output of the first assignment together with the modified availability of the workers (which is reduced by one for the assigned worker) are the input for the second assignment. This assignment is the workers' allocation for the second period. Once again the availability of the workers is updated and the third assignment is performed according to the new data. This procedure is repeated until the worker allocation is performed for all periods. Actually, the main model is replaced by N p number of simplified models where N p is the number of periods in the planning horizon. Note that, from the second assignment, a constraint must be imposed to the next models that guarantees that the difference between availability of the different workers does not exceed one : A i -A j ≤ 1 ∀i, j ∈ I, i j. The procedure of this algorithm is shown in figure (7.2).

In the beginning of the algorithm, the availability of all of the workers (A i ) is equal to the number of days that each worker is authorized to work (WD i ). After each assignment, the availability of the workers who have been assigned, is reduced by one. To avoid infeasibility, an additional constraint must be added to the main (primal) constraints. According to this procedure, the availability of the workers must be zero after the assignments of the last period, which means all of the operators have worked all authorized number of days. Because of discarding the factor of "period" in this method, the complexity of the problem and, consequently, the computational time are greatly reduced.

7.3/ HYBRID HEURISTIC ALGORITHM

The third solving method, presented in this thesis, is a hybrid heuristic algorithm for the sequencing generalized assignments. The algorithm is a greedy heuristic combined with a local search. Its starts from the best possible solution and moves to the feasibility. Four principal steps of the algorithm are as follows : 1. Choosing the best possible solution (without caring about feasibility), 2. Going towards the feasibility, 3. Applying two-exchange neighbourhood for improving the solution and finally, 4. Developing the algorithm for the sequential assignment. Figure 7.3 shows the principal steps of the algorithm in summary. It is explained in more detail in the next sections.

7.3.1/ SELECTING THE BEST SOLUTION

In the assignment matrix, the columns represent the jobs and the rows represent the workers. The elements of the matrix present the decision parameters. In this study, the operating times of the operators at different jobs are considered as the decision parameters. For the classical assignment problem, the first step of the algorithm is to select the best score in each column. This score presents the minimum operating time for the corresponding job, and the row number of the selected score presents the most appropriate worker for the job. In this way, a primal solution is found which is the best possible solution. Most of the time, the obtained solution is infeasible because of the overlapping, where a worker is selected for more than one job or a job is assigned to more than one worker. For the generalized assignment problem where more than one worker is needed in a workstation, obtaining the primal solution is more complicated. As an example, if a workstation is composed of three jobs (operators), three best scores must be selected from its related column. Note that, in this case the columns of the assignment matrix represent the workstations. Figure 7.4 shows a simple example for this step of the algorithm. Once the best possible solution is obtained, its feasibility must be examined. For the feasibility evaluation, the classical assignment constraints are applied. In this way, two set of constraints must be respected ; 1. Each operator must be assigned to one and only one job, 2. Each job must be fulfilled by one and only one operator. If the primal solution is feasible, the algorithm is finished and the obtained solution is the optimum solution for the assignment problem. But if there are the operators assigned to the more than one job, in at least one job, he must be replaced by another available operator.

7.3.2/ MOVING TOWARDS FEASIBILITY

Once the primal solution does not respect all the constraints, the operators who cause the violation must be replaced by others. As an example, if an operator is assigned to the two jobs at the same time, he must be replaced in one of them by another available operator. At first, we have to choose a job for the operator reassignment. Then, for the chosen job, an available operator must be selected to take place the previously assigned operator. For this purpose, there are various possibilities which are compared and the best one is selected.

In this way, a penalty matrix with two rows is created. The number of columns of the matrix is equal to the number of available operators. A simple example of the penalty matrix is presented in figure 7.5. According to the figure 7.4, worker number 1 is assigned to two tasks (task 1 and task 3). In one of these tasks, he has to be replaced by an available worker. The workers number 2, 3 and 5 are the available workers in this example, because they are not assigned to any task in the first step. FIGURE 7.5 -Penalty matrix for replacing a multi-job worker by the vailable workers Each element of this matrix indicates the replacing penalty. For instance, the element in the first row and second column implies the penalty of replacing the violating operator (worker 1) at his first job (task 1) by the second available operator (Worker 3). The element with the minimum penalty is selected and the replacement is made. After this replacement, the assignment is re-evaluated in terms of its feasibility. If the assignment is now feasible, hence, it is considered as the output of this step and the input of the step three as is explained in the next section. If there are still the operators to which two or more jobs are assigned, another replacing penalty matrix is created and the above procedure is repeated until a feasible solution is obtained.

7.3.3/ TWO-EXCHANGE NEIGHBOURHOOD TO IMPROVE THE SOLUTION

The solution obtained through two previous steps, is a feasible solution such that each operator is assigned to one and only one job and each job is carried out by one and only one operator. In this step, a local search is developed by aiming to improve the obtained feasible solution. For this purpose, all the two-exchange possibilities are examined. the two-exchange neighbourhood in this algorithm represents another solution where two workers change their jobs or two jobs change their assigned workers. Figure 7.6 presents a 2-opt exchange to improve the solution of the assignment problem. In this example, for the task number 3, the assigned worker (worker 2) is replaced by an available worker (worker 5). The best exchange is selected and the objective function (production time) is evaluated. If the best two-exchange improves the solution, then the mentioned exchange is applied and this procedure will be repeated until no improvement is made. The output of this step is the best solution found by the algorithm for the classical assignment problem.

7.3.4/ DEVELOPING THE ALGORITHM FOR THE MULTIPLE (SEQUENCING) ASSI-

GNMENTS

The above three steps of the proposed algorithm generate the best operator assignment for one period of time. The studied problem in this research considers a series of assignments where each assignment is related to a period (day) and the assignment is developed for several periods. As mentioned before, the best assignment can not be repeated for all of the periods because of the limitations which are defined by the number of the working-days for the operators. Therefore, the availability of the operators must be considered in the algorithm. For this purpose, after each assignment, the availability variable (the number of working-days which remains) for each worker is synchronized. This synchronization is shown in figure 7.7 by a simple example. FIGURE 7.7 -Synchronization of the availability of the workers after each assignment Hence, if an operator has worked two days during the three first days and the maximum number of working-days for him is predefined to be five days, the availability variable for him at the beginning of the fourth day is three.

According to the proposed algorithm, the difference between the availability of different workers must not exceed one score (A i -A q ≤ 1 ∀i, q ∈ I and i q). In this way, after each assignment (period), for the operators with the minimum availability, their related score in the assignment matrix are replaced by a big score to avoid the same assignment for the next period. This step of the algorithm is shown in figure 7.8.

FIGURE 7.8 -Synchronization of the assignment matrix according to the availability

As can be seen in this figure, the availability of the worker 1 after the assignment of period p is 2 days whereas the availability of the worker 2, 4 and 5 is equal to 4. Therefore, this assignment is not permitted and the assignment matrix is modified so that the worker 1 is not assigned in this period. In this way, the assignment of the period p is obtained. This procedure is followed until the assignment is made for all the periods.

7.4/ DISCUSSION

As mentioned before, the generalized assignment problem is NP-hard and solving such problems by mathematical modelization and exact algorithms could be very complicated for the large scales instances. To reduce the computational times needed to solve such problems, in this chapter, three approximate approaches were proposed. These methods are not only for solving the GAP but they can be also applied to solve the sequencing generalized assignment problem (SGAP).

The first and second proposed methods are the matheuristic approaches based on the decomposition of the formulation to simplify the main mathematical model. This strategy aims at simplifying the main mathematical model and breaking that into two or more models which are more simple. The third solving method is a hybrid heuristic composed of a greedy algorithm combined with a local search. In the next chapter, these three methods are evaluated by various instances of different sizes. The efficiency, accuracy and the computational time of the proposed methods in comparison with the exact algorithm will be discussed in the following section.

NUMERICAL APPLICATION FOR SGAP'S SOLUTION METHODS

8.1/ CASE STUDY OF TWO MATHEURISTIC APPROACHES

The two matheuristic methods, which have been presented in the previous chapter, are evaluated in this section by a real setting case study. Actually, the studied manpower planning problem, which is presented in the format of the sequencing generalized assignment problem, is applied in a part of a truck assembly line consisting of three workstations and fourteen tasks. The layout of the tasks is 4-5-5. It means four tasks are placed in the workstation number one, and five tasks in two other workstations. The production cycle time of this assembly line is eight minutes thus the task executing time of the workers must not exceed eight minutes. The workstations are placed in series and the production time for one article is calculated by the sum of the processing time of all of the workstations. The manpower planning is performed for a duration of one week (seven days). The operators are authorized to work five days, thus they have two off-days per week whereas the production system that works all seven days of the week. Twenty workers are available for executing fourteen daily tasks during a week. All of the workers are able to perform all of the tasks but their capacities are different, and the execution time of a task depends on the capacity of the worker. The objective of the problem is the assignment of the best worker to each task so that the production time of an article (sum of the workstations' processing time) is minimized. This problem is modeled as an SGAP using mixed integer programming approach (as explained in the previous section) and solved by the exact algorithm using Gurobi solver. To obtain the optimal solution through this approach, a computational time of four hours (1.7 * 10 4 ) is needed. On the other hand, the presented SGAP, which is an extension of the generalized assignment problem, is an NP-hard combinatorial optimization problem. Hence, in this thesis, two matheuristic approaches (as explained in chapter 7) are presented for solving the sequencing generalized assignment problem. These methods are able to solve the studied problem in a few seconds instead of 1.7 * 10 4 seconds where the deviation from the optimal solution is less than 1%.

The SGAP is a novel extension of the GAP which is presented in this research, thus, there is no benchmark instances in the literature. Therefore, in order to generalize and validate the proposed matheuristic approaches, a total of 27 test problems are simulated by generating random numbers for the different factors. In fact, there are four fundamental factors in such problems as the number of periods, the total number of tasks, the number of workstations and the number of tasks in a workstation. Table 8.1 shows the description and the variation domain of the factors to which the computational experiments is done.

Most important factors of the sequencing generalized assignment

Factor Description Variation domain tasks number of tasks for worker assignment 12-100 workstations number of workstations in the planning 3-20 task/workstation average number of tasks in each workstation 3-30 period duration of the planning 1-7 The efficiency of the solving approaches is evaluated by using an experimental design on the problem parameters. The generated instances are solved for different values of the presented parameters (table 8.1) by employing three different solving approaches. This analysis is performed for 3, 4, 10 and 20 workstations with 12, 14, 20, 40, 50, 90 and 100 tasks, on the 1, 2..,7 periods. The computational results of the experimentations are shown in the table (8.2). Note that the objective value of the model (PT) presents the production time needed for producing one article. The production time for one period is calculated by the sum of the processing time of the workstations and PT in the case of the multiple periods is calculated by the sum of the PT of the individual periods. In the table (8.2), the computational time needed for solving the problem is indicated by CT (the unit is second) ; and E max presents the maximum error of the approximated approaches in comparison with the exact optimal solution obtained by Gurobi.

As shown in the table of the computational results, the computing time (CT) is significantly decreased by using two approximated algorithms so that for the studied assembly line (3 workstations with 14 tasks) both of algorithms, solved the manpower planning model in less than one second whereas the computing time of the Gurobi algorithm for 7 periods is more than 4 hours. The approximated solutions have a very slight deviation from the optimal ones. The errors of both of the algorithms are less than 1%. For the studied problem (on 7 periods) the error of the Sequential method is less than two-phase method (0.13% vs 0.24% ) but the two-phase is much more simple to be used. The Sequential method is limited for the users because for each period an assignment must be performed and after each assignment, the parameters of the model must be modified. Thus, for the long planning horizons, the employing this method for solving SGAPs is very complicated.

As shown in results' table, deviations of the matheuristic approaches (E max ) never exceed 1% over all the instances. The computational times of the Sequential approach highly grow by increasing the number of tasks, and the number of workstations and the difficulty of this approach grows by increasing the number of periods. The advantage of the Sequential method is the quality of its solutions which are very near to the optimal solutions. For most of the instances, the quality of the solution obtained by Sequential is better than two-phase whereas the computational time of two-phase is significantly less than the Sequential mainly in the instances with a large number of tasks. Thus we can observe that Gurobi is only efficient for solving the small size of the SGAP. Sequential 8.2 -Computational results : Application of matheuristic methods to solve SGAP algorithm seems to be very efficient for medium sized instances and the two-phase algorithm performs very well on the tested large sized instances. Further experiments should be undertaken to confirm these conclusions. As an example, for an SGAP problem with the planning horizon of 100 periods, the Sequential approach is extremely complicated with 100 steps and it needs 99 times of manipulation whereas two-phase algorithm is easily able to solve this problem with 2 steps in a few seconds.

Computational results

Comparison of the three solution methods

8.1.2/ PRODUCTION RESULTS

The results in the previous section validate our solving approaches for various sizes of instances. In this section, the production results are compared with the current status of the real-life case. In the studied assembly line the cycle time is defined as : Production cycle time = Maximum tasks execution time + idle time In this production system, the idle time is considered as 10% of the task execution time and the manpower planning horizon is one week or seven periods. In fact, the worker assignment is repeated every week. Table (8.3) shows the results of the proposed worker assignment for each period (day) and in each workstation. The operation time of workstation equals the maximum duration of the tasks which are performed in the workstation. The production time (PT) in each day is calculated by the sum of the workstations operation times. The table (8.3) shows that the maximum task duration by the proposed assignment occurs in workstation 1 on the fifth day and is equal to 7,34 minutes. It is the objective of the proposed worker assignment model (equation 6.10) to minimize maximum task duration (as explained in section 6.3).

Production results

Day

Actually, the current production cycle time in the studied system is fixed at 9,00 minutes because of the maximum task execution time of 8,17 (The current worker assignment leads to a maximum task duration of 8,17). Hence, the workers have a minimum idle time of 0,83 in each cycle.

As could be observed in figure (8.1), the proposed worker assignment leads to a maximum task execution time of 7,34 which is 11% less than the current status. Now the production cycle time could be modified to 8,07 instead of 9 minutes. This reduction in the tasks duration and cycle time brings on a better productivity which is earned by assignment of more efficient workers to the tasks.

In this study, the approximated (matheuristic) approaches are proposed because the times needed for solving the SGAP by the exact algorithms is highly increased by growing the size of the instances. In this way, the impact of the fundamental parameters of the SGAP (table 8.1) on the computational time of the exact solving method is analyzed. This evaluation is shown is figure (8.2). Note that all computing times in this figure correspond to the exact algorithm by employing Gurobi solver.

8.1.3/ ANALYSIS OF THE PARAMETERS AND SOLVING APPROACHES

As seen in the figure (8.2-a), the solving time by the exact algorithm is exponentially increased by growing the planning horizon. Thus, for a long planning horizon even if the size of the instance on other parameters is small, the computing time is extremely large. As a result, the exact algorithm is not an efficient approach for solving SGAPs with the long planning duration. Figure (8.2-b) shows the variation of the computing time as a function of the number of tasks. These results correspond to the small number of workstations (3 and 4) and different number of tasks (from 12 to 100). As shown in this figure, increasing the computing time as a function of the number of tasks is not very extensive but it can be estimated by a linear function with a small slope. Hence, the impact of the duration of the planning on the computational time is much more important than the number of tasks. In figure (8.2-c) the computational time is evaluated by different number of workstations. It can be concluded that the computational time varies linearly but the slope is bigger than figure (8.2-b). It means the impact of the number of workstations is more important than the number of tasks and less important than the planning duration.

The last analysis about the computational times is done by considering the ratio of the number of tasks to the number of workstation. This ratio presents the average number of the tasks which are placed in each workstation. The variation of the computing time as a function of this ratio is also linear with a small slope like the number of tasks. As a result, the problem is much more complicated to solve by the exact algorithm, where the duration of the planning increases.

Generally, the approximated methods are analyzed by deviation of their solutions from the optimal and the computational time needed to solve the problem. As shown in table 8.2, the computational time of two-phase method is always less than 5 seconds even for the large size instances. About the Sequential method, the computational time varies as a function of the size of the instances. As an example, for an instance with 50 tasks and a planning horizon of 7 periods, the computing time of the sequential is 1191 seconds whereas the two-phase algorithm that solve this instance in less than 4 seconds. Therefore, two-phase algorithm is more efficient than the Sequential from a point of view of computing time. On the other hand, the errors of both methods are quite slight and vary from an instance to another. Hence, a precise analysis on the errors of two matheuristic approach has been performed as shown in figure (8.3). In this figure, the deviations of two proposed solving approach for the SGAP are analyzed over several instances of different sizes.

In this figure, the deviations of the solving methods for the SGAP are shown as a function of the planning duration. In most cases, the deviation stays the same or slightly increases by growing the length of the planning horizon. This feature guarantees the efficiency of our methods for the large size instances. The accuracy of both methods on all of instances is reasonable (more than 99% ). In addition, the error of the Sequential method is mostly less than the two-phase method. Hence, it can be concluded that the Sequential is generally more efficient than two-phase from the point of view of accuracy. By analyzing the figures (8.3-e), it can be seen that the error of the sequential method is quite near to zero when the number of tasks increases. Finally, figure (8.3-f) shows that when the number of tasks in each workstation increases the deviation of two-phase algorithm is less than Sequential.

The numerical application results show the efficiency of the proposed methods. Each FIGURE 8.3 -Evaluation of the deviations of "two phases" and "sequential" solving approaches in comparison with the optimal solutions obtained by Gurobi.

method has the advantages and the restrictions and no one can dominate over another one. As a consequence, the best solving approach for an SGAP is related to the sizes of different factors of the problem, the accuracy which is needed, and the limitation level on the computing time.

8.2/ CASE STUDY OF HYBRID HEURISTIC APPROACH

After evaluation of the matheuristic methods in the previous section, in this section the proposed hybrid heuristic approach, which was presented in section 7.3 to solve SGAP, is analysed by another case study. As mentioned in the previous section, a production system has been considered to evaluate the proposed solution methods for the SGAP.

For this system, a sequential daily assignment is needed to manage the operators during a week. The studied production system is a truck assembly line consisting of the workstations, machines, operators, ... The considered part of this assembly line contains three workstations in which there are respectively four, five and five jobs in parallel. The system works seven days per week whereas the operators have five working-days and two offdays per week. Therefore, for these three workstations, fourteen (4 + 5 + 5) operators are needed per day where the system needs twenty (14 * 7/5 = 19, 6 ∼ 20) available operators for the weekly manpower planning. The production cycle time in the system is eight minutes and each operator, depending on his capacities, has different operating times at different jobs which are between seven and eight minutes. It means the more efficient operators in each job, have the operating times near to seven minutes.

According to the structure and the restrictions of the studied production system, all four operators in the first workstation have to carry out their jobs in less than eight minutes. The processing time of the mentioned workstation is equal to the maximum operating time of the four operators working in this workstation in parallel. Thus in each workstation, there is a critical operator who determines the processing time of the workstation. The objective is to find the best job assignment to reduce total production time (the sum of the processing time of the three studied workstations) for one product.

For solving the mentioned generalized assignment problem, we have proposed a mixedinteger mathematical model as explained in section 2. This model is solved for a planning horizon of one week by employing an exact solving software named Gurobi. As a result, the optimum assignment (workforce schedule) and its related objective value (production time) are obtained. The assignment of the operators during the first period is presented in table 8.4. This table shows the structure of the studied production system and the problem considered in this research. As shown, the best operator is assigned to each of the jobs so that the processing time of the corresponding workstation is minimized. Among four operators which are assigned to the workstation number one (WS 1), the operator number nine (O9) or the job number one (J1) correspond to the maximum operating time. The operating time of this operator/job determines the processing time of the workstation. There are three workstations in series, thus the total production time is equal to the sum of the processing times of the workstations.

Manpower planning and production time for the first period

The generalized assignment is an NP-hard problem and hence the computational time to solve such problems is highly increased by raising the size of the assignment matrix. Therefore, a heuristic algorithm for the GAP is presented that is able to solve the large size sequential and generalized assignments in a few seconds. Both of two solving methods have been employed to solve the considered problem on the studied assembly line. The results of the solving methods for the different numbers of periods are compared in table 8.5. As shown in the table, by increasing the length of the planning horizon, the computational time for solving the problem by the exact method is exponentially grown. For the considered instances, the proposed heuristic algorithm is able to solve this sequential assignment with a very small deviation from the optimal solution, less than 1%, where the computational time is highly decreased. Note that the planning horizon for the job assignment in the considered case study in real-time is one week (seven periods or days). The last column of table 8.5, where P = 7, shows that the exact method solves this instance in about five hours (17000 seconds) whereas the heuristic approach spends just ten seconds to attain a solution quite near to the optimal solution. From the CT columns of the table, it can be concluded that the heuristic algorithm seems to be very efficient in the computational time even when the number of planning period is raised.

Gurobi vs

8.3/ CONCLUSION

In this chapter, a manufacturing system has been considered as the case study to evaluate the proposed solving approaches for the assignment problems. As the studied production system consists of the tasks in parallel and in series hence, we have adapted our problem with the generalized assignment problem. Because of the length of the planning horizon, which consists of multiple periods, the time dimension also imposed to the assignment problem and the term sequencing generalized assignment problem (SGAP) is proposed for such problems.

The considered worker scheduling problem has been modeled using mixed-integer programming by employing GAP structure. The mathematical model is solved for the case study by an exact approach using Gurobi solver. The results illustrated the disability of the exact approach for this problem. Thus two approximate methods based on the matheuristic approach and also a hybrid heuristic algorithm are proposed for the SGAP. A total of 27 instances of different sizes are solved by three mentioned methods. Two matheuristic approaches have been completely analyzed by different factors and size of the instances. The computational results showed the efficiency of the proposed approximate approaches for the considered instances. These methods were able to solve the SGAPs with the large sizes in a few seconds with a very slight deviation from the optimal solution. 9 HOME HEALTHCARE ROUTING AND SCHEDULING PROBLEM

9.1/ INTRODUCTION

In this part of thesis, the human resource planning in the home healthcare system is studied. This problem can be considered as an integration of the worker assignment and vehicle routing problems. The home healthcare system, as a particular type of the home delivery service systems, is a growing scope of application in the manpower planning and operations research domain. Typically, a home healthcare system is composed of the staff members, patients, and the needed services by the patients. The planning of such systems consists of assigning the patients' services to the staffs and constructing the routes for each staff member. Accordingly, both vehicle routing and assignment problems (AP and VRP), which are the well-known operational research problems, have the key roles in Home Healthcare Planning Problem (HHPP). As each one of the staff members is allocated to the multiple services during a day, the assignment part of the problem must be formulated by considering the Generalized Assignment Problem (GAP) characteristics.

Since the needed services have the starting and ending times and the staff members must arrive before the starting time, the vehicle routing part of the studied problem can be viewed as a VRP with the time windows. Hence, for developing an optimal planning in a home healthcare system, we deal with a hybrid combinatorial optimization problem.

The objective of this research is to obtain the optimal services schedules for each one of the staff members so that the total and individual distance travelled by the staffs would be minimized. A distinguishing characteristic of the studied problem is that the planning is developed on a horizon of multiple periods (e.g. one week or one month) by considering the number of working-days and off-days for the staffs. The maximum and minimum number of working hours per day for each staff are also counted in the studied problem.

In the modelization phase of the research, both aspects of the problem (assignment and routing) are formulated together in a same model by employing mixed-integer programming approach. As the mathematical model is highly complicated to be solved by the exact algorithm, we develop a novel matheuristic approach based on decomposition of the formulation to simplify the model and reduce the computational time needed to solve the problem. r : Maximum number of services which can be assigned to an employee during a day ;

NP :The maximum number of periods on which one employee is authorized to work during a working-day.

INT jpd : Matrix of the services needed by the patients ; e.g. if patient j needs a service in period p of day d, the corresponding INT is equal to 1; Otherwise is equal to 0.

DIS jk : The distance between patient j and patient k.

SETS

A variation range must be defined for each index (dimension) of the model. This range is predetermined by the sets as follows : x i jpd : Binary ; equals to 1 if employee i is assigned to patient j in period p of day d ; otherwise 0.

I = {1, 2
w i jpd : Binary ; equals to 1 if period p of day d is the first period of a service needed by patient j and this service is assigned to employee i ; otherwise 0. y i jpd : Integer ; if period p of day d is the first period of a service needed by patient j which is done by employee i, it presents the ordinal number of services which employee i carries out during day d. For example, if a service is the 3 rd service of employee i during day d and this service is for patient j and it starts in period p, in consequence, y i jpd = 3 ; u i jds : Binary, equals to 1 if s th service of employee i in day d is on patient j ; Otherwise 0.

T i jkds : Binary, equals to 1 if employee i has a travel from patient j to patient k after his s th service ; (He is assigned to patient j as the s th service and he is assigned to patient k as the (s + 1) th service).

T I id : The distance travelled by employee i during day d. x i jpd + k∈J-j

x ik(p+1)d ≤ 1 ∀ i ∈ I, j ∈ J, p ∈ P -, d ∈ D (9.7) T I id (9.20) The first set of constraints (equation 9.4) ensures that if a patient needs a service, one and only one employee is assigned to this service. Equation 9.5 guarantees that an employee can not be assigned to more that one patient in a period. The next set of constraints (equation 9.6) prevents the employees to work more than authorized working-hours during a day. The set of constraints presented in equation 9.7 ensures that if an employee works on a patient in a period, he can not work on another patient in the next period, because the model considers a travelling time of one period for the movement between two patient's homes. Hence, an employee can not start a service just after ending the previous service. The constraints 9.8 are about the services which last more than one period. These constraints ensure that if an employee is assigned to a period of a service, he will be assigned to other periods of this service. It means one and only one employee is assigned to a service even if the service lasts multiple periods. The equations 9.9 and 9.10 are the non-linear constraints that imply a change in the decision variables and introduce a set of novel variables for the next steps. These binary variables (w i jpd ) represent only the first period of the assigned services. The constraints 9.11 produce another set of integer variables (y i jpd ) that shows the ordinal number of the services which are done by an employee during a day. For example, y 1274 = 3 signifies that employee 1 is assigned to patient 2 in the 7 th period of day 4 as his 3 rd daily task. The index of period in these variables signifies only the starting period of a service. It means, in the mentioned example, if a service last three periods as 7, 8 and 9 ; then y 1274 = 3 but y 1284 = 0 and y 1294 = 0. The constraints 9.12 and 9.13 carry out a change of variable from y i jpd (assignment of the employees to the periods of day) to u i jds (assignment of employees to the services) which are the binary variables. As an example, "u 1234 = 1" implies that the 4 th service assigned to employee 1 during day 3 is on the patient 2. The constraints 9.14 ensure the ordinal nature of the variables u i jds on index s. It means for an employee in each day, second service can not be on while his first service in this day is off.

x i jpd + l∈I-i x l j(p+1)d ≤ 1 ∀ i ∈ I, j ∈ J, p ∈ P -, d ∈ D (9.8) w i jpd = x i jpd × (1 -x i j(p-1)d ) ∀ i ∈ I, j ∈ J, p ∈ {P | P ≥ 2}, d ∈ D (9.9) w i j1d = x i j1d ∀ i ∈ I, j ∈ J, d ∈ D (9.
Note that all changes in the variables from the x i jpd to the u i jds are carried out to integrate the vehicle routing problem in the assignment model. Now, by using the variables u i jds , the sequence of the patients which are visited by an employee can be obtained. Thus, the distance travelled by every employees in each day and during the whole of the planning horizon is calculated. The equation 9.15 formulates a set of variables that represent the travels between two services for each employee. In this model, the variables T i jkds perform the transferring phase from the assignment problem to the vehicle routing problem. Hence, these constraints imply that an employee's movement occurs once two consecutive services are on two different patients. Thus, the employee must travel from the first patient to the second one. By equation 9.16, the daily distance travelled by each employee is calculated. The total distance travelled by each employee during the planning horizon is calculated by equation 9.17. The constraints 9.18 and 9.19 respectively represent the maximum of the total distance and the daily distance traveled by one employee. Finally, constraints 9.20 indicate the total planning distance which is obtained by the sum of the employees' travelling distances.

The mathematical model presented above aims to minimize the travel distances by considering the routing and assignment constraints together with additional constrains of the studied problem.

9.4/ DISCUSSION

This chapter concerned the human resource planning in a home healthcare system. This planning problem has been considered as a combination of the generalized assignment and vehicle routing problems. In the assignment phase, the staff members are assigned to the patients (needed services by the patients), and in the vehicle routing phase, the sequence of patients is determined for each staff. At first, the description of the problem was presented in detail. Then, a mixed-integer mathematical model composed of both aspects of the problem was proposed in a united form. The elements of the model, as the parameters, variables, objective functions and constraints were explained in the last section of this chapter. Three objective functions were considered in the problem formulation as follows : The total distance travelled by all of the staff members (Planning distance) ;

The distance travelled by a staff member during a working-day ; The distance travelled by a staff member during the planning.

The united model presented in this chapter is an optimization approach that takes into account all aspects of the problem simultaneously in the same model. The high complexity of the model persuades us to apply an approximate approach to solve the studied problem, because the presented model is not able to solve large scale instances. To simplify this model which is strongly NP-Hard, in the next chapter, a matheuristic optimization approach is presented for this problem that considers both aspects but in the different models as the steps of the approach. In this study a matheuristic optimization approach containing three steps is proposed to optimize the home healthcare routing and scheduling problem. As mentioned before, the needed services is given to the optimization approach as a data. Other various parameters, as presented in section 9.3.1, must be defined by the users and given to the model. The first step of the algorithm aims to determine the number of staffs needed to cover all the required services. It takes the matrix of services (INT ) and other parameters as the inputs, and the output of this step is the optimal number of required staffs (NB). The second step takes into consideration the number of staffs as the input and aims to create the daily packages (sets) of services by considering daily restrictions of the staffs. In this study, a daily package of services implies a set of services which should be assigned to an employee during a day. Hence, the results of this step are the packages of services and their characteristics. Two most important characteristics of the packages are the travel distance T qd and the number of working-periods (working-hour) NPQ qd attributed to each package. These results are used by the third steps as the input. The third and last step of the algorithm is to assign each daily package to a staff. As an example, if a staff is assigned to the first package in the first day and the travel distance of this package is 50km, and in the second day he is assigned to the package number three with the travel distance of 25km, the travel distance on the planning horizon of two day for this staff is 75km. Figure 10.1 shows the steps of the proposed matheuristic algorithm. The objective function of the presented model (equation 10.1) determines the minimum number of staffs by which the needed services during the whole planning horizon can be covered. The first and second sets of the constraints (10.2 and 10.3) determine the number of patients who need the service in each period. Hence, the periodic needed staffs is obtained. As mentioned before, the employees can not be assigned to another service just after ending a service because of the travelling time consideration. It means they need to travel from a patient to another and it takes one period. Therefore, for the calculation of the needed staffs in each period, the services which are started in the subsequent period (S I jP+1d ) must be considered as well. The constraints 10.4 signify that the daily needed staffs is obtained from the maximum periodic staffs during the day. As an example, for a day containing three periods, where 10, 12 and 9 staffs are needed for the first, second and third periods respectively ; the needed staffs for this day is equal to 12.

The number of authorized working-hours for the employees is imposed to the model by constraints 10.5. According to this equation, the number of daily staffs is obtained by "total hours of the services which must be covered during the day" divided by "maximum number of authorized working-hours per day for each staff". Hence, there are two variables that determine the minimum number of staffs needed for each day (EP d , ET d ). The real number of daily staffs is the maximum of these variables for the relevant day. Similarly, the number of needed staffs to cover all the planning horizon is the maximum of the daily needs (as presented in the objective function).

After determination of the number of staffs, the packages of the services must be constructed. Each package is to be assigned to a staff. A package contains a number of services which are in the same day. Note that, the number of working-hours of a package must not exceed the maximum authorized working-hours of a staff. Furthermore, the number of packages in each day must not exceed the number of staffs. A mathematical model is presented to construct the daily packages of services as presented in following.

L = {1, 2, ..., NS }; Set of the services in one package ; 10.3.3/ ADDITIONAL VARIABLES B ql jsd : Binary variables for representing the packages of services ; Where B ql jsd = 1, if the s th service of patient j in day d is considered as the l th service of package q ; and B ql jsd = 0 otherwise.

NPQ qd : The number of working-periods for package q in day d. These variables present the working duration of the packages. For a package, the working duration is calculated by sum of the duration of the services which are placed in the package.

F ql jkd : Binary variables to represent the movements in every packages ; Where F ql jkd = 1, if the l th service of package q in day d is on patient j and the (l+1) th service of this package is on patient k. It means, there is a movement from patient j to patient k after l th service.

T qd : The travel distance related to the package q during day d. It indicates the distance travelled by an employee during day d if he is assigned to package q in this day.

T max : Maximum distance travelled of a package during a working-day. It presents the travel distance of the package with maximum movements.

10.3.4/ MODEL FORMULATION

Minimize T max = Max qd {T qd } (10.6)

S ub ject to :

q∈Q l∈L B ql jsd = p∈P S IN jpds ∀ j ∈ J, n ∈ N, d ∈ D; (10.7) j∈J s∈S B ql jsd ≤ 1 ∀ q ∈ Q, l ∈ L d ∈ D; (10.8) l∈L j∈J s∈S B ql jsd ≥ 1 ∀ q ∈ Q, d ∈ D; (10.9) l∈L j∈J s∈S B ql jsd ≤ NS ∀ q ∈ Q, d ∈ D; (10.10) l∈L j∈J s∈S B ql jsd × PS jsd ≤ NP ∀ q ∈ Q, d ∈ D; (
(q+1)1 jsd ∀ q ∈ Q -{NB}, d ∈ D; (10.13) j∈J s∈S B ql jsd ≥ j∈J s∈S B q(l+1) jsd ∀ q ∈ Q, l ∈ L -{NS }, d ∈ D; (10.14) F ql jkd ≤ s∈S B ql jsd ∀ q ∈ Q, l ∈ L, j, k ∈ J, d ∈ D; (10.15) F ql jkd ≤ s∈S B q(l+1)ksd ∀ q ∈ Q, l ∈ L -{NS }, j, k ∈ J, d ∈ D; (10.16) F ql jkd ≥ s∈S B ql jsd + s∈S B q(l+1)ksd -1 ∀ q ∈ Q, l ∈ L -{NS }, j, k ∈ J, d ∈ D;
(10.17)

T qd = l∈L j∈J k∈J F ql jkd × DIS jk ∀ q ∈ Q, d ∈ D; (10.18)
The mathematical model aims to balance the travel distances of the packages. For that purpose, a mini-max equation (10.6) is proposed to formulate this target mathematically ; where T qd presents the travel distance related to package q in day d. The objective function of the model minimizes the maximum travel distance of the packages. The first set of constraints (10.7) ensures that each one of the services is assigned to the packages. The second set (10.8) guarantees that each position of a package must be attributed to maximum one service. The constraints 10.9 signifies that every packages must contain at least one service per day. This assumption means that no one of the daily packages is empty. The number of services in each packages is limited by the constraints 10.10. By this equation a package in each day can not contain more than authorized number of services. For this restriction, parameter NS is employed because each daily package must be assigned to an employee. In addition to restricting the number of services, the working duration of the packages must be limited. This restriction is imposed to the model by equation 10.11, where parameter PS indicates the duration of the services and NP the maximum authorized working periods for a staff during a day. As mentioned before, a package is equivalent to a working day of a staff. Accordingly, for the package limitations, we use the same parameters as the staffs' ones such as NS and NP which were presented in the previous sections. The constraints 10.13 signify the order of precedence for allocating the packages to the services. According to this equation, the second package can not be allocated before the first package, the third one can be allocated after the second package and so on. Similarly, the constraints 10.14 guarantee the order of assignment of the positions inside a package. It means, in a package, the first position is assigned before the second position and the third one after the second and so on. The S ub ject to : The third and last step of the algorithm is to assign the daily packages of services to the employees in an optimal manner. For this optimization sub-problem, a mathematical model based on the assignment problem (AP) has been proposed. The objectives of this model (equations 10.19, 10.20, 10.21) are the same as the united model presented in section 9.3, to compare our matheuristic approach with the exact algorithm. The first and second sets of constraints (10.22, 10.23) are the classical constraints of the assignment problem. The equation 10.22 signifies that each one of the daily packages must be assigned to one and only one employee and the equation 10.23 implies that the staffs are not authorized to do more than one package of services during a working-day. It means an employee is either in his working-day and thus he is allocated to one package of services, or in his off-day hence no package is assigned to him. The third set of constraints (10.24) implies that the proposed assignment problem is an extended version named sequencing assignment problem. These constraints indicate that the problem concerns a sequence of assignments (one for each day) and each staff must work during a limited number of days. It is assumed that the employees have a number of working days and a number of off-days during the planning horizon.

i∈I A iqd = 1 ∀ q ∈ Q, d ∈ D; (10.22) q∈Q A iqd ≤ 1 ∀ i ∈ I, d ∈ D; (10.23) d∈D q∈Q A iqd ≤ ND ∀ i ∈ I; (10.24) d∈D q∈Q A iqd × NPQ qd × H ≤ UH ∀ i ∈ I; (
The constraints 10.25 and 10.26 concern the limitation on the number of working-hours per day. Its guarantee the respect of the maximum and minimum limits on the workinghours for each staff during his working-days. The equation 10.27 is to calculate the distance travelled by each staff during a day. It is calculated by using the distance of the daily package which is assigned to the staff. Note that, the distance attributed to each package was obtained in the previous step of the algorithm. Similarly, the total distance travelled by an employee during the planning horizon is obtained by equation 10.28. It is calculated by the sum of the daily distances travelled by the employee. Finally, the equations 10.29 , 10.30 and 10.31 concern the objective functions calculations. Note that, the planning distance (T T ) in this model is obtained from the sum of the operators' distances travelled on the whole of the planning.

The output of this step, as the last step of the algorithm, is the solution of the studied human resource planning problem. This solution defines the best (not necessarily optimal) planning for the staff members and presents the objective values of the planning.

10.5/ DISCUSSION

The procedure of the presented matheuristic approach was developed in an interface by using the Gurobi solver. The interface extracts the solution of each step and converts them to the parameters to be used in the next step. The mathematical model of each step is programmed by using the GMPL language and the solution of each step is obtained by solving the GMPL model employing the Gurobi solver. The parameters of the first step of this approach are almost the same as the parameters of the united model presented in the previous chapter. They are the main parameters of the problem. The output of the first step of the algorithm together with some of the main parameters constitute the parameters of the second step. Likewise, the output of the second step constitutes a part of the parameters of the third step. The output of the third step, as the last step of the algorithm, is the solution of the problem which is obtained by this approach.

In the next chapter, the proposed algorithm is evaluated on a set of instances of different sizes and compared with the united model which was presented in the previous chapter.

In fact, solving the united model by using the Gurobi solver, as the exact method, obtains the optimal solution of the problem. In this way, the proposed matheuristic, which is an approximate optimization approach, is compared with the optimal solution obtained by the exact method.

the staff size needed for the planning. In the studied instance, the maximum staff size is attributed to the first period and is equal to four. The values in this table are per kilometer. As shown, the longest distance is between patients 2 and 10 which is 20km and the shortest one is 5km between patients 1 and 4, between 2 and 4, between 1 and 10, also between 4 and 10. By considering these values and according to the sequence of the patients assigned to the staffs (table 11.2), the distance traveled by each staff are calculated. Consequently, the values of the three objective functions of the proposed home healthcare scheduling model are calculated. By solving the model, the results of the optimization approach contains the optimal sequence of the patients to be visited and it's related distance to be crossed by each staff. For the mentioned example, the results are shown in table 11.4. This table shows the results of the planning for a duration of one day. The objective of the planning is to minimize three different criteria as T I max , T D max and T T . In fact, the optimization approach determines the best sequence of patients for each staff so that all of the needed services are covered with a minimum travel distance. In addition, there are various other considerations such as the daily and weekly working-hours, working-day and off-days, trip time,... As shown in the results of the mentioned example (table 11.4), during the given day, the staff 1 (I1) performs 4 services and works for 5 hours. He has 3 trips, the first is from patient one J1 to patient four (J4), second is from patient four to patient three (J3) and the third is from patient three to patient four. The total displacement for this staff during the studied day (T I id ) is 21km. The trip distances during this day for other staffs are respectively, 15, 10, and 14km. The planning horizon of the studied instance is one day, and hence the criterion T D i , which is obtained by the sum of the daily displacement, is equal to the criterion T I id ; (T

Numerical results of the case study

D i = d∈D T I id , & D = {1} =⇒ T D i = T I id ).
The maximum trip distance is for staff number one with 21km and the planning distance (T T ), which is the sum of the distances travelled by all of the staffs, is 60km.

11.2/ COMPUTATIONAL RESULTS

As mentioned before, for solving such combinatorial optimization problems, which are composed of the assignment and routing problems, two solution approaches are proposed in this research. At first, a united mixed-integer programming approach is presented and then a three steps matheuristic method is proposed as well. A set of simulated instances are produced and solved by both solution methods to compare them by considering all three objective functions separately. Three parameters as the planning horizon size, the number of patients and the number of staffs vary from one instance to another. Two criteria are used to compare the methods as the objective function value and the computational time. The computational time means the time needed to solve the instance. The computational results are presented in table 11.5. Note that, the increasing patient size do not necessarily lead to the higher staff size. The staff size must be calculated and it depends on the instance and the number of services that the patients need.

In this table, the columns of "Value" present the value of the objective function and the columns of "CT" present the Computing Time needed to solve the problem. The first instance concerns the planning of four staffs to cover the services required by tens patients over two days. In this instance, the maximum distance by an employee during a day (T I max ) is 51km, and the maximum total distance travelled by an employee during the planning horizon, which in this instance is two days, (T D max ) is also 51km. For this example, the optimal planning distance (T T ), the distance travelled by all staffs during the whole planning horizon, is 119km. Two solving approaches are employed as the "United MIP" and "Matheuristic". The united MIP signifies the united Mixed-Integer Programming. The MIP model is solved by Gurobi, which is an exact MIP solver, and results in the optimal solution. The matheuristic is an approximate method to solve the problem more quickly.

As can be seen in the table 11.5, for the first example, the matheuristic generates the optimal solution for the T I max and T D max with a considerable reduction in computing time.

For the objective function T T , the matheuristic obtains a solution (121km) very closed to the optimal (119km), where the gap is less than 2%, but the computing time is reduced from three seconds to less than a second. Although the matheuristics are the approximate methods, in most of the studied random instances, our matheuristic generates the optimal solution as can be seen in the results. As an example, for the objective function T I max , the matheuristic obtains the optimal solution for 30 instances among 31 random samples. The only case in which the matheuristic can not reach to the optimal is for the planning on 2 days, for 30 patients. Note that the unit of the computing times (CT) in table 11.5 is the second and the time limit for the solver is set at 10000 seconds. In certain instances, the solver is not able to find the optimal solution in the time limit such as the planning for the 30 patients over 2 days with considering the objective function T D max .

Numerical results of the case study

11.3/ STATISTICAL ANALYSIS

To evaluate the proposed matheuristic, a comprehensive analysis on the "proportion of optimal solutions which are obtained" and "the computational time needed to solve the problem", is carried out. 11.6 shows the number of instances for which each solution method obtains the optimal solution. Generally, for the studied instances, the united model is slightly more efficient than the matheuristic in this aspect, because it solved 81 instances to optimality (87%) whereas the matheuristic obtained the optimal solution for 77 instances (82%). The number of optimal solutions for different objective functions is presented separately. This table shows that for the considered instances, the matheuristic is very efficient for the objective function T I max , because it solved all of the instances to optimality in the time limit defined for the solver and is less efficient for the objective function T D max , because only 21 instances (67%) are optimally solved. On the other hand, another statistical analysis is performed on the computational times which is shown in table 11.7. According to this table, for the studied instances, the matheuristic approach is much more efficient than the united mixed-integer programming (MIP) approach because for 76 instances (90%), the matheuristic obtains the optimal solution more quickly than the united model. The analysis is made on the only instances that the optimal solutions are obtained in the time limit. As can be seen, for the objective function T I max , all instances are solved to optimality, but for the T D max , the number of considered instances is 28 and for the T T only 26 instances are solved in the time limit. The table 11.7 shows that for all 28 considered instances with the objective function T D max , the matheuristic is more quickly than united model. For the objective function T I max , only for 3 instances (9%) the united model obtains the optimal solution before the matheuristic.

Furthermore, as can be seen in table 11.5, the computational time needed to solve the problem varies depending on the duration of the planning, the number of patients and the number of staffs. Hence, an statistical analysis is made on the variation of the computational time considering each one of the mentioned parameters separately. At first, the assessment is performed based on the duration of the planning. Eight different lengths of duration are studied for the problem as shown in the results table : 2, 3, 4, 5, 6, 7, 10, and 14. The variation of the computational times depending on the duration of the planning for both solving approaches is presented in figure 11.1. The analysis is made on the three objective functions (T I max , T D max , T T ) separately. Note that, the computational time for each duration is calculated by the average of the CTs of the instances with considered duration. For example, the CT for the objective function T I max corresponding to the duration 2 is obtained by : (3 + 19 + 752)/3 = 258s for the united model, and (1 + 7 + 22)/3 = 10s.

In this example, the forth instance (30 patients) is not considered because the solver does not obtain the optimal solution in the time limit.

11.4/ COMPARISON OF SOLUTION METHODS Figure 11.1a shows that for the objective function T I max , the matheuristic method is always faster than the united model. Likewise, for two other objectives (figures11.1c and 11.1b), the matheuristic mostly obtains the optimal solution more quickly than united model. According to these figures, the variation of the computational time does not follow a specific model as a function of planning duration, but it can be concluded that the objective function T I max is less time consuming for the solver than other objectives.

The second analysis on the computational time is made based on the number of patients.

Because for each number of patients there are several instances, similar to the last analysis, the average values are considered for each number of patients. The instances with 10, 15, 20, and 30 patients are assessed and shown in figure 11.2.

After analysis of three different objectives, it can be concluded that the computational time needed to solve the problem highly increases with the number of patients. As three figures (11.2a,11.2b,11.2c) show, the computational times of the matheuristic are always lower than the united model for different numbers on patients. The difference between the CTs of two solution methods is significant mainly for the objective function T D max (figure 11.2b). Another result which can be clearly seen, is the ability of the proposed approaches to solve the small and medium sizes (from the point of view of the number of patients) of the considered problem in the reasonable time. Figure 11.2a shows that the solution methods, especially the metheuristic, are very efficient for solving the problem with the objective T I max for less than 20 patients. Similarly, figure 11.2c shows that the matheuristic is a effective method for the problem with objective T T with less than 15 patients.

The third analysis is made on the variation of the computational time based on the number of staffs. As shown in the results table, the instances with 4, 5, 6, 7, 8, 9 and 10 staffs are solved. The variation of CTs depending on the number of staffs by considering three different objectives are separately shown in figure 11.3.

This assessment shows that the computational times of the matheuristic with different number of staffs is mostly lower than the united model. According to the figure 11.3a, the solution approaches are highly efficient for solving the problem with the objective T I max , while the number of staffs are lower than or equal to 9. The three figures 11.3a, 11.3b and 11.3c show the increase in the computational time with the increase in the number of staffs. Obtaining a function to model the variation of the CT depending on the number of staffs is overly complicated because the variations are irregular, but it can be concluded that the solution methods are not able to solve very large sizes of problem in the reasonable time. The figure 11.3c shows that the difference between matheuristic and united model, by considering the objective T T , for the medium instances is considerable but for the large instances they converge towards the same value. As a result, our proposed approaches, especially the matheuristic, are much more suitable if we consider the objective function T I max for the problem.

The two solution approaches proposed in this study, were evaluated by it's computational The results show the efficiency of our matheuristic for the medium-size instances.

11.5/ CONCLUSION

The human resource planning in a home health care system was studied in this research.

The targeted planning concerns the assignment of the staff members to the patients services for a duration of multiple days in which the patients services and consequently the staff assignment vary from a day to another. This problem was formulated by using the properties of the sequencing generalized assignment problem which is a novel variant of the assignment problem. Hence, a mixed-integer mathematical model was presented for the studied problem. This model contains two different aspects of the home health care planning problem : Assignment and Routing. In the assignment phase, the staff members must be assigned to the patients services. The sequence of patients, which must be visited by each staff, is determined in the routing phase. The consideration of the time in the assignment part of the model and also for determining the routes for the staffs is another contribution of this research. By this additional dimension, the proposed combinatorial model becomes greatly complicated. This research proposed a three-phases matheuristic approach based on the decomposition of formulation to simplify the studied optimization problem. The two programming approaches (combinatorial MIP model and matheuristic approach) were implemented by applying the GMPL programming language. The accuracy and the computational time of both methods were evaluated by 31 instances of different sizes. The Gurobi solver was applied to solve the instances. A statistical analysis were performed on the computational results. This analysis shows that both methods solve the problem to optimality for more than 80% of the studied instances.

Obtaining the optimal solution for 82% of the instances by the proposed matheuristic, which is an approximate approach, proved the efficiency of this approach. Another statistical analysis on the computational times needed to solve the problem, were performed in this study. It shows that for 90% of the studied instances, the matheuristic approach is more efficient than the combinatorial MIP model in the computational time aspect.

IV CONCLUSION AND PERSPECTIVES 125

This thesis contains three main parts as follows : 1. Worker assignment and job rotation considering ergonomic criteria ; 2. Workforce scheduling by using sequencing generalized assignment formulation ; 3. Integration of the worker assignment and vehicle routing problems. In the first part, a mathematical method is proposed to determine an ergonomic adequation level between jobs and workers in a manufacturing system. In this way, the personal capacities of the workers and the jobs requirements are analyzed by using the ergonomic criteria. Then, the linear utility functions are employed for determining the ergonomic appropriateness between operators and jobs. A regression analysis showed that this appropriateness has an impact on the efficiency of the workers. According to this analysis, the operating times of the workers in each job depend on their ergonomic compatibility with the job. To minimize the production time of the studied system, the most efficient worker must be assigned to each job. For this assignment problem, a mixed-integer mathematical model is presented in which the objective is to improve the productivity by considering the impact of the ergonomic factors on the efficiency of the workers. The model generates the optimal daily worker assignments for a given planning period (multiple days) by respecting the operator restrictions as well as the workstation and production constraints. It determines which worker performs which job in which working-day in an optimum manner. The numerical application illustrates that the ergonomic considerations in the job assignment has an important impact on the production cycle time.

In the second step of the first part, the objective of the worker assignment is changed. In this step, the assignment of the jobs to the workers is not based on their efficiency or their operating times, but it is based on the workload of the jobs. Actually, the workers are exposed to different workload levels by working in different jobs, because the studied manufacturing system is composed of the heterogeneous jobs from the ergonomic point of view. In comparison with the first step in which the productivity was targeted, second step aims at developing a job rotation planning to balance the daily physical workloads on the workers. Hence, the chapter 4 of this thesis presented a specific type of job rotation in which the rotations occur only inside the predefined groups. This strategy needs less cost and time for learning the staffs in comparison with the classical job rotation and balances the physical workloads exposed to the operators of each group. In this way, an ergonomic analysis was carried out for the jobs and the its physical workloads were evaluated by different ergonomic criteria. The workload levels were classified into high, medium and low categories. Afterwards, a mixed integer mathematical model was developed to obtain optimal sequences for the group job rotation by aiming to balance the daily physical workloads on the workers. Furthermore, the constraints of the proposed model prevent the operators to face the successive high workloads.

The proposed approach was applied to plan the workforce scheduling for a truck assembly line. The computational results and its related statistical analysis demonstrate that the workload scores are balanced among the operators. The model is well adaptable for other production and service systems to reduce the risks of the WMSDs and occupational diseases. The proposed job rotation method in this chapter can be favourable for the systems in which the skills required by different jobs are largely different.

As a result, in the workforce scheduling of chapter 3, the workload on the operators is ignored whereas in chapter 4, the efficiency of the workers and productivity are ignored. Hence, chapter 5 of this thesis proposed a multi-objective programming approach to balance the workloads on the operators and also improve the productivity by assigning most efficient workers to the jobs. Both productivity and ergonomic aspects are considered simultaneously in the workforce scheduling model which is presented in this chapter. In fact, a job rotation platform for the studied manufacturing system has been implemented by developing a mathematical model. The integration of the worker assignment and the job rotation problems constructs a novel combinatorial optimization problem in the production domain. In this optimization problem is expanded by considering the heterogeneous workers, different task execution times for the workers, capability of the workers and different workload levels of the jobs. The production cycle time as the productivity and the daily workload as the ergonomic criteria have been targeted in the presented problem. By solving the mathematical model of the job rotation, the optimum sequence of jobs is obtained for each worker. Different scenario, according to the decision maker or user point of view, can be defined for this problem and for each scenario one or more optimum solution is calculated. The numerical application illustrated the adequacy and efficiency of the proposed mathematical model to optimize both objectives simultaneously. However, three different mathematical models for the human resource planning in manufacturing system with specific regard to the ergonomic considerations are developed in the first part of this thesis.

In the second part, according to the structure of the studied manufacturing system, the human resource planning is modelled based on the Generalized Assignment Problem (GAP). The GAP, as an enlarged variant of the assignment problem, is a well-known problem in the operational research domain. This adaptation helped us to well organize the structure of our human resource planning model. Because of the length of the planning horizon, which consists of multiple periods, the time dimension is also imposed to the assignment problem and the term sequencing generalized assignment problem (SGAP) is proposed for such problems. Moreover, two extra considerations are added to the classical generalized assignment problem. The first one is the restriction which is imposed on the working-days and off-days of the operators. The second consideration is the dynamics of the assignment which can be changed from a period to another. Because of these additional concerns, the problem is much more complicated than the classical GAP which is an NP-complete problem. The considered worker scheduling problem has been modelled using mixed integer programming by employing GAP structure. This model is solved by employing Gurobi mixed-integer solver for the various sizes of the problem. The solver, as an exact solving approach, is only able to solve the small-scale problems. Three approximate approaches have been proposed for solving such problems in the medium and large sizes. Hence, this thesis presented a hybrid heuristic and two matheuristic algorithms to solve GAP and SGAP. Various instances of different sizes are solved by three mentioned methods. The proposed approximate approaches have been completely analyzed by different factors and size of the instances. The computational results show the efficiency of the proposed approaches. These approximate algorithms present the solutions with a very slight deviation from the optimal ones. The numerical results demonstrate the great reduction in the computational time in comparison with the Gurobi solver.

After studying the human resource planning problem in the manufacturing system in the two first parts, this optimization problem was considered for a home healthcare system in the third part of this thesis. This planning problem concerns the assignment of the staff members to the patients services so that the distance travelled by the staffs would be minimized. The duration of the planning is multiple days in which the patients services and consequently the staff assignment vary from a day to another. This problem was formulated mathematically by using the properties of the SGAP which was presented in the second part of this thesis as a novel variant of the assignment problem. Considering the characteristics of the studied system, an integration of the SGAP with the Vehicle Rou-ting Problem (VRP) was presented in this part. Hence, the proposed model contains two different aspects of the home health care planning problem : Assignment and Routing.

In the assignment phase, the staff members were assigned to the patients services. The sequence of patients, which must be visited by each staff, is determined in the routing phase. This thesis proposes a three-phases matheuristic approach based on the decomposition of formulation to simplify the studied combinatorial optimization problem. The matheuristic algorithm was developed by applying the GMPL programming language. It's accuracy and computational time was evaluated by various instances of different sizes.

The Gurobi solver was applied to solve the instances. A statistical analysis were performed on the computational results. This analysis shows the proposed method solve the problem to optimality for more than 80% of the studied instances. Obtaining the optimal solution for 82% of the instances by the proposed matheuristic, which is an approximate approach, proved the efficiency of this approach. Another statistical analysis on the computational times needed to solve the problem, were performed in this study. It shows that for 90% of the studied instances, the matheuristic approach is more efficient than the exact algorithm in the computational time aspect.

For the future works, three following axes are the possible directions to expand the researches which are carried out in this thesis. The first axis is the consideration of the human resource planning problem. In the first part of this thesis, a job rotation based on the workloads of the jobs was presented. In this way, considering the productivity factors into the job rotation model combined with the ergonomic issues may be an interesting axis for the future studies. On the other hand, we can consider uncertainty concerns for the estimation of the workload scores by employing the Fuzzy logic or Statistical approaches. The analyzing of the learning-forgetting effect and learning costs can be other ways as the further researches. Moreover, considering the the idle times for the workers and correlation between processing time and workload of the jobs can be studied as the futures works.

For the sequencing generalized assignment problem which is presented in the second part, the uncertainty considerations, fuzzy or stochastic SGAP and multi-objective consideration could be the interesting future research of this novel problem. In this thesis, the classical SGAP is solved by applying two mat-heuristic approaches. For the solving method, divers exact or approximated approaches (heuristics, combinatorial heuristics, meta-heuristics and hyper-heuristics) could be developed for the SGAP. With regard to the solving methods proposed for the GAP in the literature, developing a genetic algorithm, tabu search, Bees algorithm for the SGAP or it's extensions could be the interesting prospects for the future researches. A combinatorial heuristic containing one or more of the mentioned meta-heuristics may be another future solution approach for the SGAP. Furthermore, in the second part of this thesis, a hybrid heuristic algorithm is proposed to solve the GAPs and SGAPs. Developing and generalization of this algorithm and comparing that with the meta-heuristic approaches can be the interesting subjects of the future researches.

FIGURE 2 .

 2 FIGURE 2.1 -Assembly line containing workstations in series and jobs/Workers in parallel

FIGURE 2 . 3 -

 23 FIGURE 2.3 -Generalized assignment problem for 3 workers and 6 jobs

FIGURE 3 .

 3 FIGURE 3.1 -Utility function of height for workstation 2

  starting time of the workstation j in day d ; -P d j = processing time of workstation j in day d ; -F d j = ending time of workstation j in workday d ; -C d = production cycle time in workday d ;

FIGURE 3 . 2 -

 32 FIGURE 3.2 -Production cycle time in D6

WL j :

 j The global workload level of job j. G, Y, R : If the global workload evaluation of the job results in a respectively, green, yellow or red level of workload. S (G), S (Y), S (R) : The severity scores of the workload colors.

  W l : Coefficient (Impact factor) of criteria l for calculating the global workload of the jobs. m : Number of workers to be allocated, I = {1, ..., m} ; n : Number of jobs to be assigned, J = {1, ..., n} ; r : Number of ergonomic criteria which are analyzed in the job evaluation, L = {1, ..., r} ; t : Number of periods during a day, P = {1, ..., t}, P -= P \ {t} ; s : Number of days during the planning horizon, D = {1, ..., s}, D -= D \ {s} ; q : Number of workstations in the system, G = {1, ..., q}, G -= G \ {q} ; -K g : Number of jobs which are placed in workstation g, ∀g ∈ G ; -α, β, γ : Quantitative workload scores for, respectively, high, medium and low level of workload. (In this research : 2,67 , 1,57 and 1)

Figure 4 .

 4 Figure 4.1 shows the efficiency of the proposed model on the balancing of the workloads mainly inside the workstations.

52CHAPITRE 5 .∀

 5 MULTI-OBJECTIVE JOB ROTATION BY ERGONOMIC CONSIDERATIONS 5.2.3.2/ JOB ROTATION AND WORKER'S CAPABILITY CONSTRAINTS k ∈ K, i ∈ I, p ∈ P -, d ∈ D

  x i jp ≤ b i ; ∀ i = 1, ..., m; p = 1, ..., l;

:

  N p : Number of periods in the planning horizon ; n : Number of available workers during the planning ; m : Total number of tasks in all of the workstations ; WS k : The tasks which are developed in workstation number k ; M k : Number of tasks which are developed in workstation k ; E i j : Efficiency of worker i for executing task j. Execution time of task j by the best worker ; t i j : Execution time of task j if it is performed by worker i ; PCT : Production cycle time ; WD I : Number of working days of the operators during the planning horizon ;

  and ending time of workstation k in period p ; PT p : Production time in period p ; 6.3.3/ MODEL FORMULATION OBJECTIVE FUNCTION

m:

  Total number of workers for the assignment. I = {1, ..., m} n : Total number of jobs. J = {1, ..., n} s : Number of workstations. K = {1, ..., s} N k : Number of jobs in workstation k ∈ K. (N 1 = 4 : There are 4 parallel jobs in workstation 1) t : Number of periods in the planning horizon. P = {1, ..., t} Y i j : Operating time of worker i in job j. (Decision matrix) WS k : The jobs which are carried out in workstation k.

FIGURE 7 . 4 -

 74 FIGURE 7.4 -Selecting the best solution of the assignment matrix

  FIGURE 7.6 -Two-Exchange neighbourhoud for the assignment problem

FIGURE 8 . 1 -

 81 FIGURE 8.1 -Production cycle time

  the studied problem which must be given to the model as the constant values or matrices are presented as : m :Number of employees ; n :Number of patients ; h :Number of working-periods per day ; t :Number of days in the planning horizon ;

  , ..., m} : Set of employees ; J = {1, 2, ..., n} : Set of patients ; P = {1, 2, ..., h} : Set of periods during a day ; D = {1, 2, ..., t} : Set of days during the planning horizon ; S = {1, 2, ..., r} : Set of services needed by the patients.

9. 3

 3 .2/ DECISION VARIABLES The variables are the elements of the model which must be optimally determined by solving the model. The objective of the model depends on the values of the variables. The variables of the proposed model are as follows :

T D i :Ob jective 3 :

 i3 The distances travelled by employee i during the planning horizon. (Sum of the daily travel distances for each employee) T I max : Maximum distance travelled by an employee during one day. T D max : Maximum distance travelled by an employee during the planning horizon. T T : Total distance travelled by all of the employees during the planning horizon. (Total planning distance) 9.3.3/ OBJECTIVE FUNCTIONS The objective functions of the model are the intended purpose of the problem which is modelled mathematically. Three objectives are considered in the studied problem as follows : Minimize Z 3 = T D max (9.3) The first objective function (Z 1 ) aims at minimizing the total planning distance ; e.g. the sum of the daily distances travelled by all of the employees for all of the planning days. The second objective function (Z 2 ) aims at minimizing the maximum distance travelled by one employee during a day. The aim of the third objective function (Z 3 ) is to minimize the maximum distance travelled by one employee during the planning horizon. The characteristics of the three objectives and their related advantages and inconveniences are explained as follows : -First objective : Various proposal assignments (plannings) can be easily compared by using the value of this objective. It does not consider the balancing of the travel distance among the employees. -Second objective : It results in a balanced travel distance among the employees every day ; But it does not consider the total or daily travel distance of the planning. -Third objective : Employing this objective leads to the balanced total distances travelled by each employee on the planning horizon. It does not care about the daily distance of the employees and the total travel distance of the planning. 9.3.4/ CONSTRAINTS The restrictions of the problem are mathematically formulated as the following constraints : = INT jpd ∀ p ∈ P, j ∈ J, d ∈ D (≤ 1 ∀ j ∈ J, p ∈ P, d ∈ D (≤ NP ∀ i ∈ I, d ∈ D (9.6)

  10)y i jpd = w i jpd × k∈J p q=1 w ikqd ∀ i ∈ I, j ∈ J, p ∈ P, d ∈ D (9.11) ≤ 1 ∀ i ∈ I, d ∈ D s ∈ S (∀ i ∈ I, d ∈ D s ∈ S - (9.14) T i jkds = u i jds × u ikd(s+1) ∀ i ∈ I, j ∈ J, k ∈ J, d ∈ D s ∈ S - × T i jkds ∀ i ∈ I, d ∈ D (= Max i∈I {T D i }(9.18)T I max = Max i∈I, d∈D {T I id } (

FIGURE 10. 1 -

 1 FIGURE 10.1 -Matheuristic approach for the home healthcare planning

Ob jective 2 :

 2 Minimize ZA 2 = T I max (10.20) Ob jective 3 : Minimize ZA 3 = T D max (10.21)

  10.25) d∈D q∈Q A iqd × NPQ qd × H ≥ LH ∀ i ∈ I; (10.26) T I id = q∈Q T qd × A iqd ∀ i ∈ I, d ∈ D; (10.27) T D i = d∈D T I id ∀ i ∈ I; (10.28) T I max = Max i∈I, d∈D {T I id }; (10.29) T D max = Max i∈I {T D i };

120CHAPITRE 11 .

 11 FIGURE 11.1 -Variation of the computational times depending on the planning duration

TABLE 3 .

 3 1 -Ergonomic characteristics needed by the jobsIn the next step of this work, the characterizations of the workers must be discovered. For the skill level, each operator have to pass an examination test for each job. The experience level is the number of years that the workers have already worked on the same or similar jobs. Table3.2 shows the result of the evaluation of the 4 operators in 5 different workstations. In this table WS denote the workstations. For example "WS1 :2" in the skill level row, shows that the score of the operator in the evaluation test of workstation 1 is 2/10.

		Operators' Characterizations
	Ergo factor	Operator1	Operator2	Operator3	Operator4
	Height (cm)	171	183	175		178
	Age (year)	33	40	42		26
		WS1 :5 WS2 :8	WS1 :2 WS2 :3	WS1 :10 WS2 :4	WS1 :5 WS2 :6
	Skill level	WS3 :3 WS4 :2	WS3 :7 WS4 :9	WS3 :5	WS4 :1	WS3 :2 WS4 :5
		WS5 :5	WS5 :8	WS5 :7	WS5 :2
		WS1 :2 WS2 :5	WS1 :0 WS2 :0	WS1 :6 WS2 :2	WS1 :1 WS2 :3
	Experience level	WS3 :0 WS4 :0	WS3 :4 WS4 :8	WS3 :1 WS4 :0	WS3 :0 WS4 :1
		WS5 :1	WS5 :3	WS5 :4	WS5 :0

TABLE 3 .

 3

	2 -Operators' Characterizations
	According to this table, as an example, operator 1 with 33 years old and 171cm height,
	has a skill level of 5 for workstation 1 and 2 years experiences in this or other similar jobs.
	3.2.2/ DETERMINATION OF THE ADEQUATION LEVEL BETWEEN WORKERS AND
	JOBS

TABLE 3 .

 3

		Operator1 Operator2 Operator3 Operator4 Operator5
	WS1	0.68	0.38	0.85	0.40	0.44
	WS2	0.79	0.47	0.41	0.71	0.76
	WS3	0.31	0.63	0.55	0.27	0.95
	WS4	0.25	0.92	0.33	0.62	0.59
	WS5	0.49	0.76	0.70	0.18	0.34

3 -Global utility level of the workers in different workstations 3.2.3/ WORKER ASSIGNMENT TO THE JOBS BASED ON THE ADEQUATION LEVEL

TABLE 3 .

 3

5 -Weekly workforce schedule

TABLE 3 .

 3 No of OP per week Avg Cmax Computing time 6 -Computational results Specific contributions of presented research in comparison with most related literature such as Otto and Scholl (2013), Rattanamanee and Nanthavanij (2013) and Mossa et al.

	5	9	13	180.31	17s
	6	10	14	208.76	38s
	7	11	16	234.71	95s
	8	14	20	272.34	730s
	9	16	23	-	> 10 5 s

TABLE 4

 4

.1 -Ergonomic parameters measured

TABLE 4 .

 4

2 -Prioritization of risk factors and workloads

Numerical evaluation of the jobs and worker assignment without job rotation

  .3)

	Workstation	Job	Physical Workload	(general evaluation)	Repetition	Postures	Material Handling	Force	Energy Consumption	Workload Score	per period (WL)	Assigned worker	Number of periods	during a day (P)	Daily Workload	(WL*P)
		1 Yellow 1.57 2.67 1.57 1.57 1.57	8.95	OP1	4		35.8
	1	2 Yellow 1.57 1.57 1.57 1.57 1.57 3 Green 1 2.67 1.57 1.57 1	7.85 7.81	OP8 OP9	4 4		31.4 31.24
		4 Green	1	1.57	1	1.57	1	6.14	OP14	4		24.56
		5 Green 1.57	1	2.67 1.57	1	7.81	OP2	4		31.24
		6 Green	1	1	1.57	1	1	5.57	OP3	4		22.28
	2	7 Green	1	1.57 1.57 2.67	1	7.81	OP5	4		31.24
		8 Green	1	1.57 1.57 1.57 1.57	7.28	OP11	4		29.12
		9 Yellow 1.57 2.67 1.57 1.57 1.57	8.95	OP12	4		35.8
		10	Red	2.67 1.57 2.67 2.67	1	10.58	OP4	4		42.32
		11 Green	1	1.57 1.57 1.57	1	6.71	OP6	4		26.84
	3	12 Green	1	1.57 2.67 1.57	1	7.81	OP7	4		31.24
		13 Yellow 1.57 1.57 2.67 1.57 1.57	8.95	OP10	4		35.8
		14 Yellow	1	2.67 2.67 1.57	1	8.91	OP13	4		35.64

TABLE 4 .

 4

3 -Numerical evaluation of the jobs and worker assignment without job rotation 4.2/ MODELIZATION OF THE JOB ROTATION PROBLEM

table 4 .

 4

		Workforce schedule by Group Job Rotation
	Work station	Worker	Sequence of jobs	Workload exposed P1 P2 P3 P4	Cumul load
		op1	3 → 4 → 1 → 2	7.81 6.14 8.95 7.85	30.75
	1	op8 op9	4 → 1 → 2 → 3 2 → 3 → 4 → 1	6.14 8.95 7.85 7.81 7.85 7.81 6.14 8.95	30.75 30.75
		op14	1 → 2 → 3 → 4	8.95 7.85 7.81 6.14	30.75
		op2	6 → 9 → 7 → 8	5.57 8.95 7.81 7.28	29.61
		op3	7 → 6 → 9 → 7	7.81 5.57 8.95 7.81	30.14
	2	op5	5 → 5 → 6 → 9	7.81 7.81 5.57 8.95	30.14
		op11	9 → 7 → 5 → 6	8.95 7.81 7.81 5.57	30.14
		op12	8 → 8 → 8 → 5	7.28 7.28 7.28 7.81	29.65
		op4	12 → 13 → 11 → 10	7.81 8.95 6.71 10.58	34.05
		op6	13 → 14 → 14 → 12	8.95 8.91 8.91 7.81	34.58
	3	op7	14 → 12 → 13 → 14	8.91 7.81 8.95 8.91	34.58
		op10	10 → 11 → 10 → 11	10.58 6.71 10.58 6.71	34.58
		op13	11 → 10 → 12 → 13	6.71 10.58 7.81 8.95	34.5

3

. The GUROBI solver is employed to solve our mixed-integer model and the results are shown in table

4.4.

TABLE 4 .

 4

4 -Workforce schedule by Group Job Rotation

TABLE 4 .

 4

5 -Capability of the workers

As shown in table 4.4, the worker assignment and job rotation inside the workstations are developed by considering the capability of the workers. According to this table, four operators are assigned to workstation 1 (operators 1, 8, 9 and 14 for jobs 1, 2, 3 and 4), five operators to workstation 2 (operators 2, 3, 5, 11 and 12 for jobs

5, 6, 7, 8 and 9)

and five operators work in workstation

3 (operators 4, 6, 7, 10, 13 for jobs 10, 11, 12, 13

TABLE 4 .

 4

	Workstation No of data	WL Without rotation Mean STDEV	WL by rotation Mean STDEV
	1	4	30.75	4.63	30.75	0.00
	2	5	32.45	4.92	32.45	0.27
	3	5	38.85	5.77	38.85	0.23

6 -Statistical analysis of the impact of the rotation

TABLE 4

 4

.7 -Proposed optimal job rotation in comparison with the best random rotation

  The presented model can be easily converted to a classical job rotation model by neglecting constraints 4.19 and 4.20. To validate this assumption, the model has been employed to simulate a classical job rotation on the studied system. The results of the computational simulation is shows in table4.8.

		Workforce schedule by Classical Job Rotation
	Worker Sequence of jobs	Workload exposed P1 P2 P3 P4	Cumul. load
	op1	6 → 12 → 10 → 3	5.57 7.81 10.58 7.81	31.77
	op2	1 → 6 → 11 → 10	8.95 5.57 6.71 10.58	31.81
	op3	11 → 10 → 13 → 6	6.71 10.58 8.95 5.57	31.81
	op4	14 → 4 → 3 → 9	8.91 6.14 7.81 8.95	31.81
	op5	5 → 1 → 4 → 13	7.81 8.95 6.14 8.95	31.85
	op6	12 → 11 → 14 → 2	7.81 6.71 8.91 7.85	31.28
	op7	13 → 14 → 12 → 4	8.95 8.91 7.81 6.14	31.81
	op8	9 → 8 → 7 → 12	8.95 7.28 7.81 7.81	31.85
	op9	7 → 3 → 1 → 8	7.81 7.81 8.95 7.28	31.85
	op10	2 → 9 → 2 → 11	7.85 8.95 7.85 6.71	31.36
	op11	4 → 2 → 9 → 14	6.14 7.85 8.95 8.91	31.85
	op12	3 → 13 → 8 → 7	7.81 8.95 7.28 7.81	31.85
	op13	10 → 5 → 6 → 5	10.58 7.81 5.57 7.81	31.77
	op14	8 → 7 → 5 → 1	7.28 7.81 7.81 8.95	31.85
		TABLE 4.8 -Workforce schedule by Classical Job Rotation

TABLE 5 .

 5 In fact the studied production system composed of different workstations and each workstation composed of divers jobs. According to this table, first workstation incorporates four and the second one incorporates five jobs.

2 -Workers' Operating Time

As shown in this table, one operator can be very efficient in some jobs but not very efficient in others. The first row the table shows the operating time of the worker one (I1). It can be seen that he is the best operator in the jobs one and eight (J1 , J8), but he is not very adequate for the job number nine (J9). The nine jobs presented in this table are the jobs of two workstations (WS 1 , WS 2).

TABLE 5 .

 5

	J7 J4

4 -Worker Assignment and Job Rotation based on the Workload Levels of the jobs

TABLE 5 .

 5 5 -Worker Assignment and Job Rotation based on the Operating Times of the workers

	.1	4	4.3 4.2 4.3 4.1

TABLE 5 .

 5

6 -Multi-Objective Analysis (Linear aggregation)

TABLE 8

 8

	.1 -Most important factors of the sequencing generalized assignment
	8.1.1/ COMPUTATIONAL RESULTS

TABLE 8 .

 8 4 -Manpower planning and production time for the first period

Heuristic for solving generalized assignment problem

	No of periods	Gurobi Prod Time Comput Time	Heuristic Prod Time Comput Time	GAP
	P = 1	21.30	< 1s	21.32	< 1s	0.09%
	P = 2	42.69	< 1s	42.87	< 1s	0.42%
	P = 3	64.28	40s	64.87	< 1s	0.76%
	P = 4	85.57	36s	86.15	< 1s	0.67%
	P = 5	107.00	196s	107.67	< 3s	0.62%
	P = 6	128.55	12 * 10 3 s	129.55	< 5s	0.77%
	P = 7	149.98	17 * 10 3 s	151.25	< 10s	0.84%
	TABLE 8.5 -Gurobi vs Heuristic for solving generalized assignment problem

  11.1.2/ ANALYSIS OF THE SOLUTIONSThe distances between every pair of patients are given by the company as the distance table and imposed to the model as the DIS jk parameters presented in section 9.3. A segment of the distance table is presented in table11.3.

	TABLE 11.3 -The distances between every pair of patients
		J1
	J2	14 J2
	J3	12 10 J3
	J4	5	5	8	J4
	J5	12 19 12 12 J5
	J6	16 10 20 12	9	J6
	J7	6	19 14 20	7	10 J7
	J8	14 19	6	15 19	9	11 J8
	J9	8	12 10 12 19	6	9	19 J9
	J10 5	20 15	5	15 17 18 16 18

TABLE 11 .

 11 4 -Numerical results of the case study

	Staff	Sequence of patients	Services	Hours	T I id (T I i1 )	T I max	T D i	T D max	T T
	I1	J1 → J4 → J3 → J4	4	5	5 + 8 + 8 = 21		21
	I2 I3	J3 → J8 → J8 → J6 J6 → J7 → J7 → J7	4 4	6 5	6 + 0 + 9 = 15 10 + 0 + 0 = 10	21	15 10	21	60
	I4	J7 → J1 → J9	3	4	6 + 8 = 14		14

TABLE 11 .

 11

TABLE 11 .

 11 The results of this analysis is presented in tables 11.6 and 11.7. 7 -Percentage of best computational time obtained over all instances Table

	118CHAPITRE 11. NUMERICAL EXPERIMENTS FOR THE HHC PLANNING PROBLEM
		Proportion of optimal solutions obtained
	Solution method	T I max	Objective function T D max	T T	Total
	United MIP	30/31 = 96%	25/31 = 80% 26/31 = 83%	81/93 = 87%
	Matheuristic	31/31 = 100% 21/31 = 67% 25/31 = 80%	77/93 = 82%
	TABLE 11.6 -Proportion of optimal solutions obtained
	Percentage of best computational time obtained over all instances
	Solution method	T I max	Objective function T D max	T T	Total
	United MIP	3/31 = 9%	0/28 = 0%	6/26 = 23%	9/85 = 10%
	Matheuristic	28/31 = 91%	28/28 = 100% 20/26 = 77%	76/85 = 90%

(a) 3 workstations with 14 tasks (b) 3 workstations with 20 tasks (c) 3 workstations with 90 tasks (d) 4 workstations with 12 tasks (e) 4 workstations with 100 tasks (f) 10 workstations with 20 tasks

9.2/ OBJECTIVES AND PROBLEM DESCRIPTION

The planning of the staff of a home healthcare company is considered to be optimized by applying mathematical programming. The table 9.1 shows a part of the data given by the company that presents the services needed by the patients. The company has a number of staffs (employees) available to cover these services. This study concerns the determination of the optimum planning for the staffs. The services last one or two hours, and the staffs work six to eight hours per day. It means each staff is allocated to a number of services during a day. The services assigned to an employee, are not necessarily for the same patient. Hence, they travel between patients during the day. The objective is to minimize the travel distances for each one or all the staffs.

Required services by the patients

Patient

Service1 Service2 Service3 J1 7 :00-8 :00 12 :00-13 :00 -J2

No need J3 12 :00-14 :00 --J4

18 :00-19 :00 --J5

No need J6 7 :00-8 :00 20 :00-21 :00 J7 8 :00-9 :00 12 :00-13 :00 20 :00-21 :00 J8 10 :00-12 :00 15 :00-17 :00 -J9 16 :00-18 :00 --J10

No need TABLE 9.1 -Raw data for the required services by the patients during a specified day Table 9.1 shows the services needed by ten patients (J1..., J10) during a given day. As it can be observed, some patients do not need any service in this day and others need one, two or three services. The problem contains sequence of plannings over several days, a planning for each day. Therefore, the problem can be formulated as a Sequencing Generalized Assignment Problem (SGAP) presented by [START_REF] Moussavi | Productivity improvement through a sequencing generalised assignment in an assembly line system[END_REF]. To solve this combinatorial optimization problem, a mixed-integer mathematical model is proposed. The model involves various dimensions including the patients, staffs, services, number of days considered for the planning, number of periods during a day. Many various constraints are considered in the modelization of the problem such as the number of authorized working-days for each staff during the planning, number of services which are assigned to a staff during a day, number of authorized working-hours per day,... A mathematical model is composed of the parameters which must be given to the model as the data, and the variables which are determined by solving the model. To model the problem by integer linear programming (ILP) approach, the parameters and the variables must be defined as integer or binary values. The most important parameters of the studied model are the required services which are neither integer nor binary. They are provided by the company in the format shown in table 9.1. This raw data must be converted to the numerical parameters to be applicable in our optimization model. Hence, a binary approach is used for this transformation by fixing the periods of a day. The results are shown in table 9.2 that presents the needed services by a set of binary parameters. This structured data is used in our proposed optimization approach in this study and can be used in any other mixed-integer models.

Structured daily services required by the patients

Day Period Patients J1 J2 J3 J4 J5 J6 J7 J8 J9 J10

-Structured daily services required by the patients

In this table, P1 presents the first working-hour (period) of the day, i.e., "from 7 : 00 to 8 : 00" and P14 represents the last working-hour (period) which is "from 20 : 00 to 21 : 00".

In this research, the parameters of the needed services named INT jpd (as explained in the next section) are presented as the binary numbers. Table 9.2 is an instance of the INT matrix. The other parameters, such as the duration of the planning, the number of working hours, ... are integer. Our optimization approach determines which staffs are allocated to the services needed by patients on different periods during the days. Therefore, the studied problem composed of two different aspects : 1. the assignment of the staffs to the services (Assignment Problem), 2. the distance travelled by the staffs to move from one patient to another (Routing Problem). In next sections, the problem is formulated mathematically to be solved by a mixed-integer solver. In this way, two approaches are proposed. The first is a united MIP model and the second is a matheuristic approach which are explained in the next sections.

9.3/ UNITED MIP MODEL TO INTEGRATE AP AND VRP

For the mentioned problem, an integrated MIP approach is proposed that contains both assignment and routing aspects. The objective function of the model is the travel distance which is a routing objective. The constraints involve the assignment and routing constraints. In this formulation approach, a change of variable is made to draw a correlation between the assignment and routing constraints. Considering two aspects in the same mathematical model results in a combinatorial optimization model which is presented in this section by it's related induces, parameters, variables, and model formulation consisting of objective function and constraints.

INT : (10.15, 10.16 and 10.17) define the variables of movement (F ql jkd ) inside the packages. These equations signify that there is a movement between patients j and k after the l th service of package q (F ql jkd = 1) if and only if the l th position of package q is assigned to a service of patient j and the the (l + 1) th position of this package is assigned to a service of patient k. The travel distance of the packages is calculated by equation 10.18, where any movement is multiplied by its corresponding distance. Hence, a travel distance is attributed to each package in each day.

In this step of our modelization approach, the packages of services are formed. In each day of the planning, the number of packages must be equal to the number required staff (NB) which is calculated in the first step of the algorithm. The next and the final step concerns the assignment of daily packages to the employees.

10.4/ STEP 3 : ASSIGNMENT OF THE PACKAGES TO THE STAFF

MEMBERS

The third step of the proposed approach is to assign the packages of services to the employees. Two sets of variables as T qd and NPQ qd which are obtained in the previous section, are employed as the parameters in this step. Each employee is allocated to a package in each day. The objective is to balance the total distance travelled by each staff during the planning horizon. The mixed-integer programming approach is employed to model this step which is presented as follows.

10.4.1/ ADDITIONAL PARAMETERS T qd : Travel distance corresponding to package q in day d.

NPQ qd : Number of working-periods of package q in day d.

H : Coefficient for conversion number of periods to number of hours. Here H = 1 implies that one period is equivalent to an hour.

10.4.2/ ADDITIONAL VARIABLES

A iqd : Binary decision variables for representing the assignment of packages to the employees ; Where A iqd = 1, if package q is assigned to employee i in day d and A iqd = 0, otherwise.

T I id : The distance travelled by employee i in day d. These variables present the daily movement of the staffs.

T D i : The distance travelled by employee i during whole planning horizon.

T T : Total travel distance of the planning. (The sum of the distances travelled by the employees on whole the planning)

T D max : Maximum total distance travelled by an employee during the planning horizon.

T I max : Maximum daily distance travelled by an employee.

NUMERICAL EXPERIMENTS FOR THE HHC PLANNING PROBLEM

In this part, a set of real data is employed to be used in our optimization approach. Knowing that the results of the evaluation of an approach by one sample is not reliable, a Monte Carlo Simulation (MCS) is performed to simulate the instances of various sizes.

The planning of the staffs of a home healthcare company is considered to be optimized by employing two proposed methods : the united mixed-integer model and the matheuristic approach. Table 9.1 presented in section 9.2 as a part of the data given by the company is used as the basis for simulation more instances of required services.

Based on this sample, we have generated 31 instances of different sizes. The three parameters considered for the instance generation are : 1. The number of days for the planning, 2. The number of considered patients and 3. The number of employees. The variation domain of the simulation parameters is presented in table 11.1. In the presented study, two optimization approaches are proposed to model and optimize the planning of the home healthcare staffs during a given period. The efficiency of the both methods are analyzed and compared by the simulated instances. The comparison is carried out based on the objective function values and the computational time needed for solving the problem. The mathematical model of two approaches contain three different objective functions. All three objectives present the travel distance as introduced in section 9.3. Applying the optimization approach on the considered problem results in an optimal planning for the staffs and an organized program of the visits for the patients.

Variation domain for the simulation parameters

Planning of 4 home healthcare staffs to cover 10 patients during a given day In this small instance, according to the patients columns of the table, the first patient (J1) needs two services in the first and sixth periods (P1, P6). The first service of this patient is performed by the staff number one (I1) and his second service is done by the staff number four (I4). The allocated staffs to the other patients are shown in this table in the same manner. On the other hand, the results can be displayed based on the staffs. The planning of the staffs for the considered instance is shown in the employees columns of this table. As can be seen, the first employee (I1) is allocated to four services in this day. The first service is on the patient number one (J1) and lasts one hour or one period. The second service on the patient four (J4) lasts one period, but his third service on the patient three (J3) takes two periods (P6, P7). Similarly, the planning of the other employees are presented in this table.

As mentioned before, the number of employees needed to cover all of the patients' services is not a given value but must be calculated. By employing the mathematical model presented in section 10.2, the minimum staff size for a given set of services is obtained.

According to this model, for the first period of the considered example, four staffs are needed. The model considers the services of the treated period plus the services which are started in the next period (because of the trip time consideration). In this case, there are three services in the first period and one service which is started in the second period.

For each period, the needed staff size must be calculated and the maximum one will be