Convex quadratic reformulations for solving days-off scheduling problem.

Chakir Loqman; Mohamed Ettaouil; Youssef Hami; Khalid Haddouch

Author(s)

Chakir Loqman Department of Computer Engineering, High School of technology, Moulay Ismaïl University, B. P. 3103, 50000, Toulal, Meknes, Morocco

Mohamed Ettaouil Unité de Formation et de Recherche (UFR), Scientific Computing and Computer sciences, Engineering sciences, Modeling and Scientific Computing Laboratory, Faculty of Science and Technology. University Sidi Mohamed Ben Abdellah Box 2202, Fez, Morocco

Youssef Hami Unité de Formation et de Recherche (UFR), Scientific Computing and Computer sciences, Engineering sciences, Modeling and Scientific Computing Laboratory, Faculty of Science and Technology. University Sidi Mohamed Ben Abdellah Box 2202, Fez, Morocco

Khalid Haddouch Unité de Formation et de Recherche (UFR), Scientific Computing and Computer sciences, Engineering sciences, Modeling and Scientific Computing Laboratory, Faculty of Science and Technology. University Sidi Mohamed Ben Abdellah Box 2202, Fez, Morocco

Abstract

Workforce scheduling is one of the most important and practical problems in the service of industry and continuous manufacturing settings. Solving this problem requires determining how many workers must be assigned to each of the planning periods of work time for an organization. In this paper, our main objective is to solve the days-off scheduling problem with day task constraints. This problem is naturally formulated as 0-1 quadratic programming subject to linear constraints. To solve the latter problem, we formulate it as an equivalent 0-1 quadratic programming with a convex objective function using two convexification techniques, the first one is based on the smallest eigenvalue and the second uses the semidefinite relaxation. Some numerical examples and computational experiments assess the effectiveness of the theoretical results shown in this paper.

Publication Details

Page(s) 23-31

DOI DOI not available

Published Journal: Journal of Theoretical and Applied Information Technology, Volume: 49, Issue: 1, Year: 2013

Request the full text from PASTIC