Heuristics for flow shop scheduling : considering non-permutation schedules and a heterogeneous workforce

Abstract

The flow shop scheduling problem (or FSSP) is a very common model of production systems that is well studied in the literature. However, almost all the literature focuses on the permutation FSSP, disregarding optimal and near optimal solutions that are non-permutation schedules. Besides, common practice standardizes the processing times of each operation, even when those times may vary depending on different capabilities of the machine operators, whose diversity must be considered in the scheduling process when it is significant, e.g., in Sheltered Work centers for Disabled (SWDs). In this thesis, we propose methods to solve the non-permutation FSSP, using the same time and effort as state-of-the-art methods for the permutation FSSP, and producing non-permutation schedules with better quality than permutation and non-permutation schedules produced by state-of-the-art methods. We also propose methods to solve the combined heterogeneous workforce assignment and flow shop scheduling problem (or Het-FSSP), producing solutions that compensate the different capabilities and disabilities of the workers with minor or null losses in the productivity objectives. Moreover, the heterogeneous workforce assignment may be integrated into other shop scheduling models, as we did with the heterogeneous workforce assignment and job shop scheduling problem (or Het-JSSP) with similar results.

O problema de escalonamento num flow shop (ou flow shop scheduling problem, FSSP) é um modelo de sistemas de produção muito comum que é bem estudado na literatura. No entanto, quase toda a literatura foca-se em escalonamentos permutacionais, desconsiderando soluções ótimas e quase ótimas que são escalonamentos não-permutacionais. Além disso, a prática comum padroniza os tempos de processamento de cada operação, mesmo que estes tempos variem dependendo das diferentes capacidades dos operadores das máquinas, cuja diversidade deve ser considerada no processo de escalonamento quando seja significativa, e.g., em centros de emprego para deficientes (CEDs). Nesta tese, propomos métodos para resolver o FSSP não-permutacional, usando o mesmo tempo e esforço que os métodos do estado da arte usam para o FSSP permutacional, e produzindo escalonamentos não-permutacionais com melhor qualidade do que escalonamentos permutacionais e não-permutacionais produzidos por métodos do estado da arte. Também propomos métodos para resolver o problema combinado de designação de trabalhadores heterogêneos e escalonamento de tarefas num flow shop (ou heterogeneous workforce assignment and flow shop scheduling problem, Het-FSSP), produzindo soluções que compensam as diferentes capacidades e deficiências dos trabalhadores com pequenas perdas nos objetivos da produção. Além do mais, a designação de trabalhadores heterogêneos pode ser integrada em outros problemas de escalonamento, como fizemos com o problema combinado de designação de trabalhadores heterogêneos e escalonamento de tarefas num job shop (ou heterogeneous workforce assignment and job shop scheduling problem, Het-JSSP).