Proceedings of the 2014 Industrial and Systems Engineering Research Conference

Y. Guan and H. Liao, eds.

PROPOSING A PERSONNEL SCHEDULING MODEL: THE

CASE OF MOTOROLA SOLUTIONS

Abstract ID: I1420

Abstract
Due to constant advances in technology and growing business competition, it is increasingly common for
technology companies to offer users’ training in their service portfolio. In this sense, an effective planning method
for allocating instructors to courses is necessary to prevent overload, subcontracting or idle workforce, as well as
offering a good service level to consumers. Thus, this study proposes a mathematical model for the Personnel
Scheduling Problem in the IT training industry, since there is a lack of specific approaches for training companies
with acyclic annual periods in the literature. Therefore, a case study at Motorola Solutions was performed aiming to
validate the preliminary model. By using the proposed approach, the company was able to easily identify that it was
necessary to hire more instructors, so as to avoid overloading or subcontracting, ensuring the quality of service. We
concluded the study pointing out some possible improvements for future research.

Keywords
Integer Linear Programming; Allocation Planning Staff; Case Study; Technology Company.

1. Introduction
Due to the fast pace of emerging technologies, IT (Information Technology) companies have to train their clients to
manipulate new solutions. The high degree of competition, especially in the technology arena, stimulates companies
to provide differentiated services that please the customer in the post-sale service, with the goal of improving
consumer loyalty.

The post-sale service, whether offered by the company supplying technology or by third-party specialized consulting
branches, often demands a thorough and detailed planning, sometimes with a high degree of complexity. This is due
to the number of constraints of the problem, including instructors’ limitations (e.g. capability or availability), as well
as client conveniences. We can also consider human difficulties, in which various labor laws must be respected, or
the moral of instructors related to preferences or workload. Besides, it is often important to reduce the total cost of
planning itself, either by minimizing the amount of training not met, which would imply a loss of confidence or even
fines, or the amount of recurrent subcontracts necessary to satisfy demand. Both cases would lead to a greater
burden to the service provider.

In this context, several researchers (e.g. Van den Bergh et al. [1]) have attempted to address this type of problem.
Mathematical programming methods are traditionally employed to scale and solve this and it is known in the
literature as the Personnel Scheduling problem. Using mathematical modeling, one can apply practical constraints
encountered in creating a real plan, so that the solution can be translated into a good schedule (Ernst [2]; Valouxis et
al. [3]; Van den Bergh et al. [1]). Despite several important advances in this area, there is a lack of specific
approaches for training Information Technology (IT) companies with acyclic annual periods in the literature. In
addition, practical methods that are simple to be implemented in real applications seem to lack in the literature and
few applications are found in real-scale industrial cases.

Thus, the main objective of this work is to propose an efficient and easy to understand mathematical model to
schedule the instructors (around 50) who teach courses on a weekly basis in a period of one year. This model was
implemented to meet the need of the company Motorola Solutions Brazil, where the need to provide a smart solution
to manage complex scheduling and personal training was observed. This case allowed the model to be tested on a
real problem, verifying its benefits.
 No Author 1, 2, or 3 Last Name Yet

This paper is organized as follows: Section 2 presents a literature review of the Personal Scheduling domain. Then,
Section 3 discusses the methodology employed, while in section 4 the proposed model is presented. Section 5
discusses the Motorola Solutions case and its results. Finally, Section 6 provides concluding remarks and points our
possible future work.

2. Literature Review
Since 1954, after a paper about allocation of workers in toll booths presented by Edie [4] and commented on by
Dantzig [5], a large number of articles and reports addressing complex variations of the problem and solution
methods have been published in scientific journals.

One of the first classifications of the problem was given by Baker [6], where the problem is divided into three basic
groups according to its characteristics. The first is the Shift Scheduling, which features the daily planning horizon of
staff and allocation of employees in accordance with the requirements of shifts and overlapping. The second
classification is Days Off Scheduling, where the number of working days is different from the number of days of
operation of the company, that is, it is necessary to plan days off for the workers. Finally, the third is the Tour
Scheduling which planning results from the combination of the two previous types, with companies working on
specific days of the week with multiple shifts.

Several other classifications are also used according to the method implemented to solve the problem. Ernst et al. [7]
propose the subdivision into five different categories: Demand Modeling, approaches using Artificial Intelligence,
Constraint Programming, Metaheuristics, and approaches using Mathematical Programming. Our proposal fits in the
latest strategy.

The main areas of application for the identified problem cited by Van Den Bergh et al. [1] are: services,
transportation, manufacturing, retail, military and general. The general category includes restaurants, supermarkets,
festivals and parks, among others.

Nowadays, small team management to cut unnecessary costs due to idle workforce, in addition to meet the changing
needs of workers, is becoming a common application in this area. In this sense, the problem of staff allocation
gained attention of many researchers over the past years.

In the service sector, the majority of published articles address the problem of Nurse Rostering, which aims to find
the optimal allocation of teams of nurses per shift in a specified time interval. The popularity of this topic even
culminated in an international competition among researchers, called the International Nurse Rostering Competition,
sponsored by the leading conference on the subject, the International Conference on the Practice and Theory of
Automated Timetabling. Some of the latest articles published (Valouxis et al. [3]; Glass and Knight [8]; Burke et al.
[9]) describe methods of Integer Linear Programming to find solution to the problem.

In the transport sector, the focus of studies is related to the problem of Crew Scheduling, with direct applications for
airlines and public transportation companies, addressing the concept of scheduling bus drivers, train operators and
board flights teams. Articles such as Saddoune et al. [10] and Jütte and Thonemann [11] apply the method of column
generation and combinatorial optimization to improve the quality of scales made by airlines and rail lines,
minimizing the cost of companies in this process.

Similarly, the works of Kabak et al. [12] and Zhang et al. [13], Chong and Strevell [14] respectively, demonstrate
different approaches to scheduling problems in the retail, manufacturing, and military sectors. Furthermore, several
authors address issues of staff allocation in schools or universities; however, only one article (Haase et al. [15])
where the problem was formulated with the basic characteristics similar to the one proposed in this article was
found. It presents the problem of Lufthansa Technical Training GmbH, in which the company offers 670 different
types of training courses, of which hundreds are held every year. The aim of the paper is to solve the problem of
planning the courses to maximize the profit margin of the company, given the different types of constraints. The
main similarity relates to the proposal of a non-periodic allocation for a one-year horizon.
 No Author 1, 2, or 3 Last Name Yet
Because this topic is unexplored in the literature, the work of Haase et al. [15] is a starting point to this paper, which
aims to propose a model easily understandable and simple to implement for the company, thus increasing its use.
Moreover, his model can be further refined in accordance with the training needs of companies.

3. Methodology
This study combines aspects of instrumental research with exploratory research and case study. These three aspects
are discussed below:

● Instrumental research: first of all, the proposal of a model with an optimization approach makes use of the
basic premises of the research called "instrumental", which is recommended for the field of applied
research (Martel [16]; Mattessich [17]). It “(…) refers to methodological creative activities aimed at
creating a tool to support organizations in achieving their goals. These instruments include systems,
methods, models, and components of these instruments, and tools necessary to invent them” (Martel [16]).
In this case, the proposed instrument refers to a new model in the Personnel Scheduling for an IT company.
To implement such model, we used methods of synthesis and analysis. Typically, the research instrument
makes use of a creative phase (called the "intelligence" by Martel [16]) in which the instrument is
developed. After, the validation of the proposed instrument has to be performed. In this work, several tests
of the proposed model were performed. However, the validation was only preliminary since it was not
performed extensively, i.e. in several different situations that would allow generalization. Because of that,
this work also presents characteristics of exploratory research;
● Exploratory research: this type of research aims to "(...) provide greater familiarity with the problem in
order to make it explicit or build hypotheses". It may involve, among other things, analysis of examples
that encourage understanding and can take, in various situations, the form of "case studies" (Silva and
Meneses [18]). The tests performed in this work generate hypotheses about the usefulness and the easy use
of the proposed tool, opening the door to further studies in the future.
● Case study: aims to provide conditions for a preliminary validation of the proposed model (Yin [19]).
Therefore, a real-scale industrial application was performed at Motorola Solutions Brazil.

In the next section, the proposed tool will be presented.

4. Contribution
In order to solve the problem mentioned in the last section, from formulations such as those presented by Daskalaki
et al. [20] and Al-Yakoob and Sherali [21], we propose an Integer Linear Programming (ILP) model with the main
objective of minimizing the number of employees and subcontractors to meet the total demand for training during
one year. Information about parameters, indices, variables and sets used in the model are given below.

4.1 Definitions

Indices and Parameters

𝑁 : Total of instructors;
𝑃: Total of different types of trainings;
𝑇: Total period;
𝑖 = 1, 2, ..., 𝑁: i-th instructor;
𝑘 = 1, 2, ..., 𝑃: k-th type of training;
𝑡 = 1, 2, ..., 𝑇: t-th period;
𝑑𝑡𝑘: training 𝑘 demand on 𝑡 period;

𝑀: a very large arbitrary number.

 No Author 1, 2, or 3 Last Name Yet

Decision Variables
𝑥𝑖𝑡𝑘: binary variable which is 1 if instructor 𝑖, lectured a training of type 𝑘, in the period 𝑡;
𝑧𝑖𝑡: binary variable which is 1 if instructor 𝑖 lectured any training in the period 𝑡;
𝑦𝑡𝑘: integer variable which represents the number of subcontracts to the training 𝑘, in the period 𝑡;

Sets
𝐼(𝑘): Set of Subsets that represent the index of instructors that can lecture the 𝑘-th training.

These sets can be described as: which instructors are able lecture the considered training course, e.g. if the company
has a Training 1 that can only be lectured by Instructors 2, 3 and 4, the subset 𝐼 representing this training will be
known as 𝐼(1): {2, 3, 4}.

An Integer Linear Programming Model is characterized by its ease of implementation for small data sets, which is
the case for the company considered in this study. An important question about this type of problems is its
unpredictable nature, with the possible increase of magnitude of the indexes considered, as presented in the
following sections. The model is then formulated as follows:

4.2 Mathematical Model

𝑡
(
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 ∑ ∑ 𝑧𝑖𝑡 + ∑ 𝑀𝑦𝑡𝑘
𝑖 𝑘
) (1)

𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜

∑
𝑖∈𝐼(𝑘)
(𝑥𝑖𝑡𝑘) + 𝑦𝑡𝑘 ≥ 𝑑𝑡𝑘, ∀𝑡 = 1, 2 ..., 𝑇; ∀𝑘 = 1, 2 ... 𝑃 (2)

𝑘
( )
𝑧𝑖𝑡 = ∑ 𝑥𝑖𝑡𝑘 , ∀𝑖 = 1, 2 ..., 𝑁; ∀𝑡 = 1, 2 ... 𝑇 (3)

𝑧𝑖𝑡 + 𝑧𝑖𝑡+1 + 𝑧𝑖𝑡+2 ≤ 2, ∀𝑖 = 1, 2 ..., 𝑁; ∀𝑡 = 1, 2 ... 𝑇 (4)

𝑦𝑡𝑘 ∈; 𝑥𝑖𝑡𝑘, 𝑧𝑖𝑡 ∈ {0, 1} (5)

The objective function (1) seeks to minimize the number of employees assigned, to avoid unnecessary allocation,
and it penalizes any subcontract made. This means that subcontracting only occurs in the case of infeasibility, which
can be represented by the lack of staff available or excess demand.

Constraints of type (2) serve to stress that the number of employees assigned or subcontracted in period t is
sufficient to satisfy the demand of that period for all k. It is worth mentioning that in the summation, i contains only
those instructors who can teach the training k.

In (3) we ensure that the variable 𝑧𝑖𝑡 is active if the instructor i has been given any training in the period t.

Constraints (4) force the instructor i not to work more than two periods consecutively.

Finally, the block of constraints (5) ensures the integrity of the variables 𝑦𝑡𝑘 and that the variables 𝑥𝑖𝑡𝑘and 𝑧𝑖𝑡 are
binary.

The proposed model was solved by the free linear optimization software GLPK version 4.49, using a computer with
8GB of RAM and a i5-3570K 3.4 Ghz processor.
 No Author 1, 2, or 3 Last Name Yet
5. Motorola Solutions Case
Motorola Solutions resulted from a spinoff occurred at Motorola Mobility, and is seen by many as the direct
successor of the old company founded in 1928. Known for its powerful infrastructure and high capacity for
innovation, Motorola is in Brazil since 1994, where it established a production facility and commercial offices.

Currently, Motorola Solutions provides products and services for data communication and telecommunication,
organized in two divisions: business and government. The first one develops advanced data capture, wireless
infrastructure, bar code scanning, two-way radios and business pagers, wireless broadband networks and RFID
solutions to customers worldwide. On the other hand, the government and public safety division produces analog
and digital two-way radio products, voice and data communications, security systems, wireless networking and
mobile computing, among others.

All products developed by the company comprise user training. Typically, for this subsidiary, all the trainings are
held weekly throughout Latin America, and they are scheduled through the whole year, with dates stipulated by
contractors, allowing little or no flexibility.

The number of instructors provided by Motorola Solutions is fixed and instructor one is able to give different types
of training. Due to the need to prevent overcharging instructors, an instructor is required not to work more than two
weeks in a row, when courses are offered in different cities.

5.1 Data Gathering

To validate and evaluate the model, we used data provided by the manager of the instructors covering all Latin
America, including training already undertaken and the ones still to be conducted in 2013. Furthermore, to test the
efficiency of the model we generated random scenarios by varying the number of instructors and the types of
training.

5.2 Computational Results

This section presents the data and the solution found for the real problem and demonstrates the computational time
and the results for each scenario. Table 1 contains all basic information related to all scenarios:

Table 1 – Scenarios Information

Number of Instructors Types of trainings (P) Number of periods (T)
Scenario
(N)
Motorola Solutions 4 6 45
Scenario 1 5 10 45
Scenario 2 10 20 45
Scenario 3 15 40 45
Scenario 4 20 50 45
Scenario 5 25 70 45
Scenario 6 30 85 45
Scenario 7 35 90 45
Scenario 8 40 100 45
Scenario 9 45 130 45
Scenario 10 50 150 45
Source: Authors

It is worth noticing that the value of large integer mentioned in modeling (the big “M”), was 10,000 for all scenarios.
Tables 2 and 3 show the actual demand for each type of training for a period of 45 weeks (first 22 weeks of the year
in Table 2 and the last 23 weeks in Table 3) for the case proposed by the company.

Table 2 – First 22 weeks demand

Weeks
Type
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0
2 1 0 0 0 0 0 0 0 1 2 0 1 0 0 0 2 0 0 2 0 0 0
 No Author 1, 2, or 3 Last Name Yet
3 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Source: Data provided by Motorola Solutions Ltda.

Table 3 – Last 23 weeks demand

Weeks
Type
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1
2 0 0 0 0 1 0 0 2 0 2 1 1 1 1 1 0 0 0 1 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 1 0
5 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
6 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Source: Data provided by Motorola Solutions.

The sets mentioned in Section 4 were defined as follows:

𝐼(1): {1};
𝐼(2): {1, 2};
𝐼(3): {1, 2, 3};
𝐼(4): {1, 3};
𝐼(5): {2};
𝐼(6): {1, 2, 3, 4};

The problem was solved by GLPK solver and the results obtained are displayed using Gantt diagrams in Figures 1
and 2:

Figure 1 – First 22 weeks schedule

Source: Authors

Figure 2 – Last 23 weeks schedule

 No Author 1, 2, or 3 Last Name Yet

Source: Authors

It can be noticed that there is an overload of two instructors (1 and 2), which forces to the use of subcontracting. It
happens because instructors 3 and 4 lack skills to offer trainings of high demand, in this case, trainings of type 1 and
2.

To overcome this problem, we proposed two solutions. The first would be to hire new instructors with type 1 and 2
skills, while the other solution would be training the existing instructors 3 and 4 to lecture trainings of type 1 and 2.

Besides the real problem, some additional scenarios (see Table 3) were generated in order to determine for which
sizes there is a low computational time.

The majority of scenarios presented in Table 1 shows a relatively small time to solve the problem (maximum 1
minute), but for bigger problems, the solution time lasted more than one hour; the latter were hence excluded from
this analysis. Table 4 contains information found for each scenario solved.

Table 4 – Computational Results

Used Variables Constraints Total Demand Subcontracts
Scenario Solution Time (s)
Generated
Motorola Bellow 0.1 1530 1118 47 5
Scenario 1 Bellow 0.1 2925 4941 68 2
Scenario 2 0.1 10350 18881 170 0
Scenario 3 0.3 29475 73321 195 5
Scenario 4 0.3 48150 114261 312 4
Scenario 5 3.3 83025 222701 475 9
Scenario 6 82.7 119925 327766 505 2
Scenario 7 9.2 147375 367581 646 34
Scenario 8 8.2 186300 453521 680 9
Scenario 9 139.4 271125 764461 812 38
Scenario 10 16.6 346500 1016901 891 49
Source: the authors

Comparing the results with the input data listed in Table 1, we note a small increase in initial parameters (number of
instructors and types of training), meaning the problem size grows in a combinatorial fashion; hence, the time of
solution also increases proportionately.

It is important to note that cases 6 and 9 were those with the longest solution time, and this is because these
problems have symmetries, which complicates the determination of an optimal solution.

6. Concluding Remarks
The personnel scheduling problem for IT consulting and training companies was modeled as an
integer-programming problem to determine an efficient planning. The model was previously tested within Motorola
Solutions Brazil. The solution shows an overload for the instructors.
 No Author 1, 2, or 3 Last Name Yet
The main alternatives to solve the problem identified in the company are hiring new employees or training
instructors. The first alternative is currently under study and the company is inclined to hire new employees, keeping
in view the future demands that will arise during events like the World Cup 2014 and the Olympic Games 2016 in
Brazil. The second option is not considered at the time by the company, as both instructors with a high degree of
idleness are employees of a third-party contracted by Motorola.

Considering the randomly generated scenario, it could be noted that the solution times are mostly dependent on the
demand of the artificially generated matrix. It was noted that the GLPK has not been able to solve the problem for
cases in which there were more than 100 instructors and 150 different types of training, limiting the focus of the
proposed applications for medium and small businesses. Furthermore, it is worth to say that the periods are
considered in blocks of weeks, since that was the need for Motorola.

The results achieved by the company reached the expected goals, and several sophistications to the model can be
done to make it more robust and to contemplate different cases. In this sense, a suggestion for future research would
be to improve the current model by adding the costs associated with the hiring process, outsourcing and training of
instructors. Besides, a study of heuristics for determining a good quality solution is suggested

One of the main difficulties of this study was to find articles with an applied approach for the sector because, even if
there is a vast literature on the Personnel Scheduling problem, only a small number of articles (other than the one
presented by Haase et al. [15]) exist for the sector of training companies. Thus, this paper contributes to this line of
research by providing a new model in the area.

Acknowledgements
The authors would like to thank Motorola Solutions Brazil for their support and participation in this project.

References
1. Van Den Bergh, J.; Beliën, J.; DE Bruecker, P.; Demeulemeester, E.; De Boeck, L., 2012, “Personnel
scheduling: A literature review”, European Journal of Operational Research, 226(3), 367-385.
2. Ernst, A. T.; Jiang, H; Krishnamoorthy, M.; Sier, D., 2004, “Staff scheduling and rostering: A review of
applications, methods and models”, European Journal of Operational Research, 153(1), 3-27.
3. Valouxis, C.; Gogos, C.; Goulas, G.; Alefragis, P.; Housos, E., 2012, “A systematic two phase approach for
the nurse rostering problem”, European Journal of Operational Research, 219(2), 425-433.
4. Edie, L. C., 1954, “Traffic delays at toll booths’, Operations Research, 2(2), 107-138.
5. Dantzig, G., 1954, “A Comment on Edie’s Traffic Delay at Toll Booths”, Operations Research, 2,
339–341.
6. Baker, K. R., 1976, “Workforce allocation in cyclical scheduling problems: A survey”, Operational
Research Quarterly, 155-167.
7. Ernst, A. T.; Jiang, H.; Krishnamoorthy, M.; Owens, B.; Sier, D., 2004, “An annotated bibliography of
personnel scheduling and rostering”, Annals of Operations Research, 127(1-4), 21-144.
8. Glass, C. A.; Knight, R. A., 2010, “The nurse rostering problem: A critical appraisal of the problem
structure”, European Journal of Operational Research, 202(2), 379-389.
9. Burke, E. K.; Li, J.; Qu, R., 2010, “A hybrid model of integer programming and variable neighbourhood
search for highly-constrained nurse rostering problems’, European Journal of Operational Research, 203(2),
484-493.
10. Saddoune, M.; Desaulniers, G.; Elhallaoui, I.; Soumis, F., 2011, “Integrated airline crew scheduling: A
bi-dynamic constraint aggregation method using neighborhoods”, European Journal of Operational
Research, 212(3), 445-454.
11. Jütte, S.; Thonemann, U. W., 2012, “Divide-and-price: A decomposition algorithm for solving large railway
crew scheduling problems”, European Journal of Operational Research, 219(2), 214-223.
12. Kabak, Ö.; Ülengin, F.; Aktaş, E.; Önsel, Ş.; & Topcu, Y. I., 2008, "Efficient shift scheduling in the retail
sector through two-stage optimization", European Journal of Operational Research, 184(1), 76-90.
13. Zhang, R.; Chang, P.; Wu, C., 2012, “A hybrid genetic algorithm for the job shop scheduling problem with
practical considerations for manufacturing costs: investigations motivated by vehicle production”,
International Journal of Production Economics, 145(1), 38-52.
 No Author 1, 2, or 3 Last Name Yet
14. Chong, P. S.; Strevell, M. W., 1985, “A vacation scheduling algorithm for military flight crews:
Maximizing satisfaction while maintaining military preparedness”, Journal of Operations Management,
5(2), 205-211.
15. Haase, K.; Latteier, J.; Schirmer, A., 1998, “The course scheduling problem at Lufthansa Technical
Training”, European Journal of Operational Research, 110(3), 441-456.
16. Martel, A., 1986, La recherche instrumentale sectorielle en sciences de l’administration. In: La production
des connaissances scientifiques de l’administration/The generation of scientific administrative knowledge.
M. Audet, and Malouin, J.-L. Québec: Les Presses de l’Université Laval.
17. Mattessich, R., 1978, Instrumental reasoning and systems methodology, Reidel Pub. Co..
18. Silva, E.L.; MENEZES, E.M., 2005, “Metodologia da Pesquisa e Elaboração de Dissertação”, 4th Edition,
UFSC, Florianopolis.
19. Yin, R.K., 2009, Case Study Research: Design and Methods, 4th Edition, SAGE Publications, Thousands
Oks.
20. Daskalaki, S.; Birbas, T.; Housos, E., 2004, “An integer programming formulation for a case study in
university timetabling”, European Journal of Operational Research, 153(1), 117-135.
21. Al-Yakoob, S. M.; Sherali, H. D., 2006, “Mathematical programming models and algorithms for a
class–faculty assignment problem”, European Journal of Operational Research, 173(2), 488-507.