A meta-heuristic solution approach based on mathematical programming for tour scheduling problems involving flexible scheduling policies

Creative Commons License

Yildiz Ş. A., Avci M., YILDIZ G.

JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY, vol.36, no.2, pp.823-839, 2021 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 36 Issue: 2
  • Publication Date: 2021
  • Doi Number: 10.17341/gazimmfd.660960
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Art Source, Compendex, TR DİZİN (ULAKBİM)
  • Page Numbers: pp.823-839
  • Keywords: Tour scheduling problem, meta-heuristic, mat-heuristic, flexible scheduling policies, BRANCH-AND-PRICE, SIMULATED ANNEALING APPROACH, BENDERS DECOMPOSITION, SHIFT SCHEDULES, WORK FORCE, LABOR, PERSONNEL, MODEL, FLEXIBILITY, SYSTEM
  • Dokuz Eylül University Affiliated: Yes


In service systems such as hospitals, banks, restaurants, airports, supermarkets, call centers, where customer demand changes during the day and between business days, the issue of how to schedule the employees is of great importance. The purpose of personnel scheduling in such systems is to assign the personnel at the required time and with the minimum number / minimum cost to provide a certain level of service. This personnel scheduling problem is called Personnel Tour Scheduling Problem (TSP) in the related literature. When the TSP is solved, the personnel schedules, i.e. tour schedules, which meet the personnel requirement according to customer demand varying during the day and between business days, are obtained in the relevant scheduling period. Service systems implement flexible scheduling policies such as, Flexible Shift Start Times (FSST), Shift Start Time Band (SSTB), Break Time Windows (BTW), Different Shift Lengths (DSL) / Working Day Patterns (WDP), Part Time Personnel (PTP), to create lower cost personnel schedules. The main purpose of this study is to develop a general solution method for the TSP that deals with these flexible scheduling policies simultaneously. For this purpose, a metaheuristic algorithm based on mathematical programming (mat-heuristic) has been developed which can produce good solutions within appropriate computational times for the TSP including the mentioned characteristics. Then, the effectiveness of the proposed solution method has been tested by computational analysis. The results show that the developed method can be used effectively in solving such problems.