الگوریتم های اکتشافی حریص برای تغییر برنامه ریزی نیروی انسانی

Consideration is given to a particular personnel planning problem faced by a food manufacturing company. This problem, referred to herein as manpower shift planning (MSP), seeks for the minimum workforce needed to work in each available workday shift over a given planning horizon in order to complete predetermined production objectives associated with individual production lines. We formulate MSP as an integer linear program, whose structure allows us to conjecture that it is an NP-Complete problem. We then propose two greedy heuristic algorithms for solving MSP. One for single and another for multiple workday shifts. Using results from a standard ILP optimiser together with a lower bound developed for the MSP solution, we test the performance of the multi-shift heuristic for a variety of operating environments. The results demonstrate very satisfactory performance in terms of both solution time and quality. The paper is concluded with a discussion on the results and proposals for further research.

In several companies, particularly those in the foods and pharmaceuticals industrial sectors, other than some initial processing phases, production largely consists of simple packaging operations. Packaging is accomplished on dedicated packing lines usually requiring one skilled operator and several (practically) unskilled workers. The latter are often hired under short term contracts to work on a particular workday shift (i.e. day, evening or night shift respectively). At the end of their contract, often of one month duration, workers are fired to be recalled later, if needed. Workers cannot be fired before their contract expires. In manufacturing environments as the above, total work requirements for a particular month are usually determined by a master production schedule, which gives the total production load of each packing line for all the products it produces. However, the production capacity of each packing line directly depends on the number of unskilled workers available. Therefore, a common planning problem faced by management is to decide how many unskilled workers to employ in every daily work-shift of some particular month of the master schedule so as to complete the production load of each packing line, while maximising workforce utilisation. It should be noted that the objective of maximising workforce utilisation is in most cases equivalent with minimising the total workforce to be employed. We will refer to this particular personnel and capacity planning problem as the manpower shift planning (MSP) problem. It is with the formulation and the solution of MSP, which to our knowledge has never been formally addressed in the past, that this paper is concerned. In fact, as described here, the MSP problem has been the subject of an industrial research project carried out for the Greek affiliate of a multinational company operating in the processed foods and beverages sector. Since the first published work by Dantzig [1], there has been an abundance of research related with personnel planning problems. This traditional paradigm has been primarily concerned with the determination of the workforce to be assigned to each one of a given set of work-time patterns so as to minimise total labour costs, while satisfying given labour requirements associated with each period of a planning horizon. In its most general form where one practically considers any work-time patterns, this problem is known as the tour scheduling problem. However, other simpler variations of this problem have also been studied. Jarrah et al. [2] provides a recent brief review of these variations, while more comprehensive, but somewhat dated, reviews are given in [3], [4] and [5]. All variations of tour scheduling have invariably been formulated as integer linear programs. Since these have been shown to be NP-Complete [6], most associated research concentrated in developing efficient heuristic solutions. Although it is not our intention to provide a comprehensive description of the related work, it is worth stating that these heuristics have been based on a wide range of different methodologies such as simulated annealing [7], LP-based approaches [8], [9] and [10] and goal programming [11]. There are two major differences between MSP and the above traditional personnel planning paradigm. Firstly, traditional research is concerned with deriving directly applicable detailed labour schedules. In this context, related models attempt to encapsulate all possible work specifications and minute details (such as meal breaks, days-off and part-time work) in order to realistically represent the respective operating environments. In contrast, MSP effectively tackles an aggregate capacity planning problem under general production targets and constraints. Secondly, traditional research assumes that workforce requirements for all time periods of the planning horizon are known in advance. In contrast, it is the goal of MSP to determine these workforce requirements for each individual period of the planning horizon so as to ensure that specific production objectives (using equipment of given manning needs) are completely satisfied. The remainder of the paper is organised as follows. Section 2 provides a formal definition of the MSP problem and formulates it as an integer optimisation program. It also discusses the problem computational complexity in comparison with other known problems and presents a lower bound for its solution. Section 3 presents two heuristic algorithms for solving MSP together with information concerning their order of convergence. Section 4 describes an example of using one of the algorithms for the solution of a particular application problem. Section 5 reports computational results for testing the performance of the heuristics for a variety of operating conditions. Finally, Section 6 discusses possible MSP extensions and concludes with directions for further research.

This paper has dealt with the formulation and the heuristic solution of a not previously studied personnel planning problem, we code-named MSP. The problem arises naturally during the aggregate production planning stages of particular types of industries where the available production capacity strongly depends on the workforce employed. In fact, one of the heuristics developed has now been integrated as a regular computerised decision support tool within the planning procedures of a manufacturing company. We formulated MSP as an ILP model and demonstrated its strong resemblance to the well known parallel independent machines scheduling problem for minimising makespan. Although it still remains to be formally established, on the basis of the structural similarity between the two models we conjectured that MSP (even in its simplest single-shift variation) is an NP-Complete problem. We also proposed an expression for evaluating a lower bound of the MSP solution and developed heuristic algorithms for tackling single and multi-shift problems. The multi-shift algorithm effectively extends the single-shift algorithm by incorporating a particular shift priorities selection criterion in its operating logic. Both heuristics, which may be classified as greedy algorithms, construct the solution gradually by considering one machine at a time in one single pass. This operating logic makes both heuristics extremely fast (having logarithmic order of convergence), something that allowed industrial implementation using standard commercial software and hardware tools. Moreover, as demonstrated by computational results for multi-shift environments, the heuristic solutions quality is very satisfactory. Heuristic solutions were better than those obtained by the LINGO optimiser in 50% of all test problems and deviated not more than 3% from the lower bound in most cases examined. This is not surprising considering the good performance generally reported for greedy algorithms in relation with various machine scheduling problems [14] and [17]. Since this is the first formal study of the MSP problem, there is still much ground for further research with respect to both the problem formulation per se and the refinement of the heuristic algorithms. Considering first the MSP formulation, we may attempt its generalisation by relaxing the underlying assumptions. In this context, extra features could be incorporated such as the use of less flexible workforce, limits to the workforce employed in each shift, constraints restricting particular machines to operate simultaneously or daily shifts differing in duration. Moreover, we might introduce a cost structure which would allow to differentiate workforce costs per shift. Turning to research issues related to the proposed heuristic algorithms, it might be interesting to experiment with different (and perhaps less myopic) shift selection criteria which might improve the multi-shift heuristic efficiency. More important, however, appears the adaptation of the heuristics for the solution of generalised versions of MSP such as those discussed above. Noticeably, due to their simple operating logic, the heuristics proposed may be easily adapted to deal with most of these variations. It remains, however, to be seen whether the heuristic performance will still remain satisfactory when dealing with these more complex problems. A final related issue concerns the comparison of the proposed heuristic algorithms with other approaches. As review papers indicate [18] and [19], several researchers have proposed heuristics for dealing with particular aspects of the parallel machines scheduling problem with the objective of minimising makespan. Others, in the context of different applications, have proposed heuristics for dealing with problems effectively identical to parallel machines scheduling (see, for example, [20] and [21] in relation with the modified bin-packing problem). Due to the strong similarity between these problems and MSP, it seems that with minor modifications some of these heuristics could be easily adapted for the solution of MSP. It would be interesting, therefore, first to extend some of these heuristics to cover MSP and then to compare their performance with that of the heuristics we have proposed in this paper.