Open Access
ARTICLE
Abstract
In the “shared manufacturing” environment, based on fairness, shared manufacturing platforms often require
manufacturing service enterprises to arrange production according to the principle of “order first, finish first”
which leads to a series of scheduling problems with fixed processing sequences. In this paper, two two-machine
hybrid flow-shop problems with fixed processing sequences are studied. Each job has two tasks. The first task is
flexible, which can be processed on either of the two machines, and the second task must be processed on the
second machine after the first task is completed. We consider two objective functions: to minimize the makespan
and to minimize the total weighted completion time. First, we show the problem for any one of the two objectives is
ordinary NP-hard by polynomial-time Turing Reduction. Then, using the Continuous Processing Module (CPM),
we design a dynamic programming algorithm for each case and calculate the time complexity of each algorithm.
Finally, numerical experiments are used to analyze the effect of dynamic programming algorithms in practical
operations. Comparative experiments show that these dynamic programming algorithms have comprehensive
advantages over the branch and bound algorithm (a classical exact algorithm) and the discrete harmony search
algorithm (a high-performance heuristic algorithm).
Keywords
Cite This Article
APA Style
Wei, Q., Wu, Y. (2022). Two-machine hybrid flow-shop problems in shared manufacturing. Computer Modeling in Engineering & Sciences, 131(2), 1125-1146. https://doi.org/10.32604/cmes.2022.019754
Vancouver Style
Wei Q, Wu Y. Two-machine hybrid flow-shop problems in shared manufacturing. Comput Model Eng Sci. 2022;131(2):1125-1146 https://doi.org/10.32604/cmes.2022.019754
IEEE Style
Q. Wei and Y. Wu, "Two-Machine Hybrid Flow-Shop Problems in Shared Manufacturing," Comput. Model. Eng. Sci., vol. 131, no. 2, pp. 1125-1146. 2022. https://doi.org/10.32604/cmes.2022.019754