The article focuses on the problem of a reentrant flow shop with identical jobs and makespan minimisation objective. After presenting an optimal integer programming formulation for the problem, we consider the case of unit processing times. We correct two results published a few decades ago regarding two greedy heuristic algorithms. In some cases, these algorithms lead to an optimal solution, but they are generally not optimal. We point out the advantages of each of the two heuristic algorithms and, by machine learning analysis, discuss features that differentiate between them.
Significant deterioration in the mental ability to deal with normal daily life is referred to as dementia. Alzheimer’s disease (AD) affects an estimated 60% to 80% of all people diagnosed with dementia and is considered to be the most common form of dementia among older people. Dementia with Lewy bodies (DLB) is thought to be the second most common form among the elderly,1,2 accounting for 20% of the cases at autopsy.3,4 It is estimated that, in the US alone, people have developed a type of dementia,5 with about 1.4 million of them suffering from DLB.6 Because AD and DLB are diseases related to aging, as life expectancy increases in the developed countries, these diseases become major ailments that lead to death and impose heavy financial burdens on both families and society.
In a flow shop, jobs are serially processed on a set of machines and the machine order is the same for all the jobs. In a permutation flow shop, there is an additional assumption that the order in which jobs enter the machines is the same on each machine. While the meaning of "permutation" is clear for a flow shop, it is more ambiguous for a reentrant flow shop. In a reentrant flow shop, jobs are processed on some machines more than once, leading to several ways of understanding the meaning of permutation. We indicate that different researchers use the term permutation for different assumptions. We clear up this ambiguity by identifying four definitions of permutation scheduling in the context of reentrant permutation flow shops with the cyclic pattern. In addition, we analyze the impact of these definitions on optimization and on heuristic performance with respect to the makespan objective function. We first compare optimal solutions across different permutation types, identifying cases where the best solution follows a specific permutation structure. We then extend known permutation flow shop heuristics to all four permutation definitions. Through computational experiments, we evaluate the effectiveness of these heuristics.