A Batch Scheduling Model for a Three-stage Hybrid Flowshop Producing Products with Hierarchical Assembly Structures

This paper addresses a batch scheduling problem for a three-stage hybrid flowshop consisting of a machining stage processing common and unique components on unrelated parallel machines, an assembly stage combining the components into assembled products with complex assembly structures, and a differentiation stage processing the assembled products on dedicated machines to produce different product types. The common components are the same for all products and are processed in batches, while the unique components are dedicated to respective given product types and are processed individually (one-by-one component). The goal is to schedule all the products with different assembly structures to minimize total actual flow time (TAFT) defined as total time interval of components to be processed from their arrival times to their common due date. A non-linear programming model is proposed, where small size problems can be solved optimally using the LINGO software, and large size problems is to be solved using a heuristic algorithm. The proposed algorithm consists of two sub-algorithms. The first one is constructed using a shortest processing time (SPT) based heuristic to get a job sequence as an initial solution and the second one is to improve the initial solution using the variable neighbourhood descent (VND) method with neighbourhood insert and swap move operators. In solving the problem with the algorithm, two scenarios arise, e.g., the same and the different sequences for all stages. A set of hypothetical data is generated for different hierarchical assembly structures to test the model and the algorithm, and the results show that the different sequences for all stages obtain solutions with better performances than the same ones.

Batch scheduling; Hierarchical assembly structures; Three-stage hybrid flowshop; Total actual flow time; Unique and common component

Hwang et al. (2014) explains that the common component is one that can be found in all product types, and can be processed in batches sharing the same setup time, while the unique component is one with a one-by-one processes as dedicated to a given product type. The time when the components are assembled is synchronized according to a particular hierarchical assembly structure of the products. Komaki et al. (2018) point out that an assembly structure is considered complex when it has more than one assembly operation in at least one assembly level. Maulidya et al. (2018) have developed research for the case of unique and common components but ignoring the assembly structure of products. It can be observed that the practical situation of platen and assembly roller (spare parts of a printer) production applies different assembly structures processed in the same shop floor, and there is a CNC machine that can process both a unique shaft and a common bushing for platen types, and then the first assembly operation can be conducted for both components. This is the reason for this research to be conducted.

Furthermore, Cheng et al. (2009) and Xiong et al. (2015) have discussed a final process, one that occurs after the assembly stage, for producing different product types conducted at the so-called differentiation stage. The output products can be different in colors as a result of the painting machines (Xiong et al., 2015), and they can also be different in sizes as a result of the cutting machines (Lin and Liao, 2003). These studies applied job processing but in practical situations, there are cases where a differentiation stage is conducted in batches because each dedicated machine only processes the same product type. Huang and Lin (2013) have applied a batch scheduling problem at the differentiation stage, but this is only for a two-stage differentiation flowshop.

This research aims to develop a scheduling model considering production of unique and common components with a complex assembly structure of products and apply batch scheduling to the differentiation stage. This paper uses the objective of minimizing total actual flow time (TAFT) instead of the traditional criteria, let say, completion time (see Thawongklang and Tanwanichkul, 2016), flow time (see Xiong et al., 2015), and makespan (see Natesan and Chokkalingam, 2019). The total actual flow time is defined as the time interval from the arrival times of components to be processed to their product common due date, and this objective ensures that all finished product can be completed at their due date (Halim et al., 1994b). This paper proposes a non-linear programming model for a three-stage flowshop processing unique and common components with hierarchical assembly structures and an algorithm to solve the model. The proposed algorithm adopts the VND method to improve an initial solution obtained by applying the SPT rule. The VND is a metaheuristic for solving combinatorial and global optimization problems where the neighborhoods are searched in a systematic manner, known as a steepest descent heuristic to get better solutions (Vanchipura et al., 2014). This paper is organized as follows: Section 2 discusses the model formulation, Section 3 discusses the proposed algorithm, Section 4 discusses the numerical experiences, and Section 5 discusses the conclusion.

This paper addresses the three-stage hybrid flowshop for processing different product types considering hierarchical assembly structures to minimize TAFT. Based on the numerical experiences, it is possible to use both scenarios, but the different sequence scenario provides the minimum TAFT value. This experiment is also conducted to evaluate the precedence network, of which the model is effective in providing the solution. For further research, the condition can be extended into multiple due dates to reflect the practice where the finished product is delivered in different due dates, and pre-emption is allowed. 

The authors thank the Ministry of Research, Technology and Higher Education for the dissertation research funding under contract No.011/KM/PNT/2018 with Universitas Trisakti.

Babayan, A., He, D., 2004. Solving the n-job 3-stage Flexible Flowshop Scheduling Problem using an Agent-based Approach. International Journal of Production Research, Volume 42(4), pp. 777–799

Cheng, T.C.E., Lin, B.M.T., Tian, Y., 2009. Scheduling of a Two-stage Differentiation Flowshop to Minimize Weighted Sum of Machine Completion Times. Computers & Operations Research, Volume 36(11), pp. 3031–3040

Futatsuishi, Y., Watanabe, I., Nakanishi, T., 2002. A Study of The Multi-stage Flowshop Scheduling Problem with Alternative Operation Assignments. Mathematics and Computers in Simulation, Volume 59(1), pp. 73–79

Halim, A.H., Miyazaki, S., Ohta, H., 1994a. Batch Scheduling Problems to Minimize Actual Flow Times of Parts through the Shop under JIT Environment. European Journal of Operational Research, Volume 72(3), pp. 529–544

Halim, A.H., Miyazaki, S., Ohta, H., 1994b. Lot Scheduling Problems of Multiple Items in the Shop with Both Receiving and Delivery Just in Times. Production Planning & Control: The Management of Operations, Volume 5(2), pp. 175–184

Huang, T.C., Lin, B.M.T., 2013. Batch Scheduling in Differentiation Flowshops for Makespan Minimization. International Journal of Production Research, Volume 51(17), pp. 5073–5082

Hwang, F.J., Kovalyov, M.Y., Lin, B.M.T., 2014. Scheduling for Fabrication and Assembly in a Two-machine Flowshop with a Fixed Job Sequence. Annals of Operations Research, Volume 217(1), pp. 263–279

Komaki, G.M., Teymourian, E., Kayvanfar, V., Booyavi, Z., 2017. Improved Discrete Cuckoo Optimization Algorithm for the Three-stage Assembly Flowshop Scheduling Problem. Computers & Industrial Engineering, Volume 105, pp. 158–173

Komaki, G.M., Sheikh, S., Malakooti, B., 2018. Flow Shop Scheduling Problems with Assembly Operations: A Review and New Trends. International Journal of Production Research, Volume 57(10), pp. 2926–2955

Lin, H.T., Liao, C.J., 2003. A Case Study in a Two-stage Hybrid Flowshop with Setup Time and Dedicated Machines. International Journal of Production Economics, Volume 86(2), pp. 133–143

Maulidya, R., Suprayogi, Wangsaputra, R., Halim, A.H., 2018. Batch Scheduling for Unique and Common Components in a Hybrid Assembly Differentiation Flow Shop to Minimize Total Actual Flow Time. In: Conference Paper of 19^th Asia Pacific Industrial Engineering & Management System (APIEMS) Conference 2018, Dec 2-5, Hong Kong

Maleki-Darounkolaei, A., Modiri, M., Tavakkoli-Moghaddam, R., Seyyedi, I., 2012. A Three-Stage Assembly Flow Shop Scheduling Problem with Blocking and Sequence-dependent Set Up Times. Journal of Industrial Engineering International, Volume 8(1), pp. 1–7

Natesan, G., Chokkalingam, A., 2019. Optimal Task Scheduling in the Cloud Environment using a Mean Grey Wolf Optimization Algorithm. International Journal of Technology, Volume 10(1), pp. 126–136

Thawongklang, K., Tanwanichkul, L., 2016. Application of Production Scheduling Techniques for Dispatching Ready-Mixed Concrete. International Journal of Technology, Volume 7(7), pp. 1163–1170

Utama, D.M., Widodo, D.S., Wicaksono, W., Ardiansyah, L.R., 2019. A New Hybrid Metaheuristics Algorithm for Minimizing Energy Consumption in the Flow Shop Scheduling Problem. International Journal of Technology, Volume 10(2), pp. 320–331

Vanchipura, R., Sridharan, R., Babu, A.S., 2014. Improvement of Constructive Heuristics using Variable Neighbourhood Descent for Scheduling a Flow Shop with Sequence Dependent Setup Time. Journal of Manufacturing Systems, Volume 33(1), pp. 65–75

Xiong, F., Xing, K., Wang, F., 2015. Scheduling a Hybrid Assembly-Differentiation Flow Shop to Minimize Total Flow Time. European Journal of Operation Research, Volume 240, pp. 338–354