Open Access

ARTICLE

Two-Machine Hybrid Flow-Shop Problems in Shared Manufacturing

by Qi Wei^*, Yong Wu

Ningbo University of Finance & Economics, Ningbo, 315175, China

* Corresponding Author: Qi Wei. Email:

(This article belongs to the Special Issue: Numerical Methods in Engineering Analysis, Data Analysis and Artificial Intelligence)

Computer Modeling in Engineering & Sciences 2022, 131(2), 1125-1146. https://doi.org/10.32604/cmes.2022.019754

Received 13 October 2021; Accepted 01 November 2021; Issue published 14 March 2022

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

---