Unsere Arbeitszeitpläne beeinflussen das Leben eines jeden von uns. Ungeeignete Arbeitszeitpläne können äußerst negative Auswirkungen auf unsere Gesundheit, unser soziales Leben und die Arbeitsmotivation haben. Auf der anderen Seite müssen Unternehmen und öffentliche Dienstleister ihren Personalanforderungen gerecht werden und die Qualität ihrer Dienstleistungen und Arbeitsabläufe sichern. Daher ist es von immenser Bedeutung für die Gesellschaft sowie für Arbeitnehmer und Arbeitgeber, geeignete Personalzeitpläne zu finden, die all diese Bedürfnisse berücksichtigen. Allerdings stellt die Personalplanung eine sehr komplexe Aufgabe dar, da der Suchraum aller möglichen Lösungen enorm groß ist und zugleich viele widerstreitende Bedingungen, wie etwa Arbeitsrecht, Wünsche der Arbeitnehmer und Interessen der Arbeitgeber, in der Schichtplanung berücksichtigt werden müssen. Vor allem in solchen Unternehmen, in denen die benötigte Anzahl von Mitarbeitern temporär schwankt, in denen 24 Stunden pro Tag gearbeitet wird oder die sich mit besonders komplexen oder kritischen Aufgaben (z. B. Flugsicherung oder Rettungsdienst ) beschäftigen, stellt sich die Schichtplanung als besonders problematisch dar.
Traditionell werden Personalplanungsprobleme in mehreren Schritten gelöst, die verschiedene Teilprobleme in Form von NP-hard-Problemen beinhalten (z. B. Schichtplanung, Pausenplanung, Personaleinsatzplanung etc.). Dieser Ansatz verringert zwar die Komplexität der Problemlösung, aber Schichtplanungsexperten müssen in die Lösung des Gesamtproblems mit einbezogen werden. Darüber hinaus sind die Teilprobleme stark untereinander verschachtelt und insgesamt können gute Lösungen aufgrund der frühzeitigen Entscheidung für Teilproblemlösungen nicht erreicht werden. Einige der wesentlichen offenen Fragen bei schwierigen Personaleinsatzplanungen blieben bis jetzt in der Literatur noch ungelöst: Ist es möglich, die allgemeine Personalplanung vollständig zu automatisieren und qualitativ hochwertige Lösungen ohne die Hilfe menschlicher Experten zu erhalten?
