Single Item Batch-scheduling Model for a Flow Shop with m Batch-processing Machines to Minimize Total Actual Flow Time

We propose a batch-scheduling model to minimize the total actual flow time (TAF) of parts to be processed in a flow shop consisting of m batch-processing machines. A batch-processing machine (BPM) is a machine that can process several parts at once, and the TAF of parts is the total interval time from the arrival times to the corresponding due date. In the real world, shop floors often have production lines with BPMs and multistage processes. We were motivated by a real problem in the aircraft industry and aimed to simultaneously satisfy the due dates and minimize the total time that parts spend in the shop. The problem was formulated as a mathematical model and solved using a proposed algorithm. The batch-scheduling problem is divided into batching and scheduling subproblems. The solution has been obtained by adopting backward scheduling. This paper develops a new model of flow shop scheduling problem for the shop with batch processing machines and the heuristic solution method. It provides numerical examples and their results to demonstrate the effectiveness of the proposed algorithm for solving the problem. 

Batch processor; Batch scheduling; Flow shop; Total actual flow time

A batch can be defined as several parts sharing the same setup, and the parts can be processed either on a job-processing machine (abbreviated as JPM) or on a BPM. The difference between a JPM and a BPM lies in how they process parts in a batch. A JPM individually processes all parts in a batch sequentially, whereas a BPM processes them simultaneously. This research focuses on the shop floor with BPMs found in many industries, such as that used for burn-in operations in the semiconductor industry, heating and pressure operations in aeronautical manufacturing, and hardening and soaking processes in automobiles gear manufacturing, and drying operations in the lumber industry.

        Several researchers have discussed flow shop scheduling problems. Gong et al. (2010) addressed a flow shop scheduling in steel manufacturing consisting of a soaking pit as the first stage with BPM and a rolling mill as a second stage with a JPM. The ingots (parts) in a batch will remain in the soaking pit if the rolling mill is processing another ingot, during which the soaking pit will be blocked. Fu et al. (2012) also considered the blocking constraint in a flow shop scheduling problem with two stages where the first stage is a BPM, and the second stage with a JPM follows it. The buffer between consecutive machines is limited; thus, the completed batch will keep the BPM blocked if the buffer between straight machines is full. Chen et al. (2014) also considered the blocking constraint, particularly for the flow shop scheduling problem with two BPMs with dynamic job arrivals at the first BPM.
    Liao and Huang (2011) have developed a batch scheduling model for a flow shop consisting of two BPMs with unlimited buffer capacity, and the objective is makespan minimization. To solve the problem, they created a heuristic procedure based on a Tabu search. It is shown that the heuristic is effective for solving scheduling problems with relatively many jobs. Matin et al. (2017) dealt with issues of BPMs flow shop where the parts in a batch and its batch size may change when the batch is processed on different machines. Rosi et al. (2013) developed a hybrid model of a flow shop for a sterilization plant to minimize makespan and the number of tardy jobs. They aim to reduce the number of tardy jobs (surgical kits) because late jobs will cause the surgery to be rescheduled, which brings heavy medical and economic consequences. The makespan is considered an objective because a lower makespan results in lower idle time and higher machine utilization and efficiency. On the other hand, Gokhale and Mathirajan (2011), Chou and Wang (2012), Peres and Monch (2013) have used due-date as a performance measurement. Utama et al. (2019) proposed a flow shop scheduling model to minimize energy consumption in scheduling jobs on each machine and adopted a new hybrid meta-heuristic for solving the problems.
    However, those research adopted the forward scheduling approach that may violate the due dates of jobs, and precisely represents what customers need. Many manufacturing companies intend to satisfy the due dates and minimize inventory. For fulfilling the due date, we should adopt the backward-scheduling approach, starting from the due dates of jobs and moving backward until the job is released. Meanwhile, the so-called actual flow time, defined as an interval from the arrival time of a part to the due date, was used as an objective for batch-scheduling (abbreviated as BS) problems in Halim and Ohta (1993). They showed that minimizing TAF of parts in the shop minimizes the total time that the parts spend in the shop and guarantees that the delivery of the completed parts always meets the due date. Note that TAF is based on the backward-scheduling approach. This objective was applied for various cases of BS problems (Surjandari et al., 2015; Yusriski et al., 2016; Maulidya et al., 2020), but the research pieces were for shop floors with JPMs. In reality, in many cases, the shop floor constitutes production lines with BPMs and multistage processes.
     Hidayat et al. (2013) adopted the TAF and the  backward scheduling approach for a BS problem with a single BPM processing part of a single item where the completed parts should be sent simultaneously on d as a due date. The model proposed by Hidayat et al. (2013) was developed further from different viewpoints: to tackle the condition of m heterogeneous BPMs by distributing parts to each of the m heterogeneous BPMs (Hidayat et al., 2014); to handle multiple due dates by distributing parts into all periods between two consecutive due dates (Hidayat et al., 2016); and to handle the condition of  multiple items (Hidayat et al., 2018). These researches focus on single-stage scheduling issues but demonstrate how BPM challenges differ from JPM challenges.
     However there is a need to develop a model of BS problems for a flow shop with BPMs to minimize the TAF. Such a model will extend the single-stage BS model with a BPM discussed in Hidayat et al. (2013 and 2016) to handle flow-shop processing parts of a single item delivered on d as a due date. Under the premise that the due date is far enough off to produce workable schedules, it is possible to split the problem of BS for a flow shop with BPM into two subproblems that are solved concurrently. The first subproblem is determining the number of batches and the size of each batch. The second sub-problem is the scheduling of the resulting batches.

The BS problem for the m-BPM flow shop with the backward-scheduling approach was solved by dividing it into batching and scheduling subproblems. To attain  minimum, the solutions of two subproblems must be minimal. In the batching subproblem, the number of resulted batches (N) is minimum when N equals the rounded-up value of . Rounding up is done if  is not an integer so that there is one batch with size n- (N-1) c and (N-1) batches where the batch sizes are c. On the other hand, if  is an integer, all batch sizes equal c. The solution in the scheduling subproblem will be minimum if the sequencing of N resulting batches follows the Theorem; i.e., . The starting and completion times of each batch on each BPM are determined in three simple steps. First, the completion time of the last batch processed on the last machine (  must be equal to the due date,  and . Second, completion time batch  processed on  must be determined. In the flow shop, the sequence determined using the backward-scheduling approach ensures that and  and so on until and . Third, the schedule at  which has the highest processing time, must be determined, and  and , and so on are obtained until  and . Finally,  and  schedules for i = 2, 3,..., N for k = 1,2,..., m, are determined referring to the  schedule, flow shop provisions, and the backward-scheduling approach. These three steps were devised based on backward scheduling. The proposed model is limited to problems of single item parts with an common due date. Further research can be to cover the condition of multiple items demanded at multiple  due dates.

    This work was supported by funding from Direktorat Riset dan Pengabdian Masyarakat, Deputi Bidang Penguatan Riset dan Pengembangan, Kementerian Riset dan Teknologi/ Badan Riset dan Inovasi Nasional Republik Indonesia. ID Proposal: 112de821-2cea-4b30-908c-477a9d95f273.

Chen, H., Zhou S., Li, X., Xu, R., 2014. A Hybrid Differential Evolution Algorithm for A Two-Stage Flow Shop on Batch Processing Machines with Arbitrary Release Times and Blocking. International Journal of Production Research, Volume 52(19), pp. 5714–5734

Chou, F.D., Wang, H.M., 2012. Minimizing Total Weighted Tardiness on Parallel Batch-processing Machine Scheduling Problems with Varying Machine Capacities. Applied Mechanics and Materials, Volume 110, pp. 3906–3913

Fu, Q., Sivakumara, A.I., Li, K., 2012. Optimization of Flow-shop Scheduling with Batch Processor and Limited Buffer. International Journal of Production Research, Volume 50(8), pp. 2267–2285

Gokhalea, R., Mathirajan, M., 2011.  Heuristic Algorithms for Scheduling of a Batch Processor in Automobile Gear Manufacturing. International Journal of Production Research, Volume 49(10), pp. 2705–2728

Gong, H., Tang, L., Duin, C.W., 2010. A Two-Stage Flowshop Scheduling Problem on a Batching Machine and a Discrete Machine with Blocking and Shared Setup Times. Computers & Operations Research, Volume 37(5), pp. 960–969

Halim, A.H., Ohta, H., 1993. Batch-scheduling Problems Through the Flow Shop with Both Receiving and Delivery Just in Time. International Journal of Production Research, Volume 31(8), pp. 1943–1955

Hidayat, N.P.A., Cakravastia, A., Samadhi, T.M.A., Halim, A.H., 2013. A Single Item Batch Scheduling Model on a Batch Processor to Minimize Total Actual Flowtime of Parts through the Shop. In: Proceeding Asia Pacific Industrial Engineering and Management System, Cebu, Philippines

Hidayat, N.P.A., Cakravastia, A., Samadhi, T.M.A., Halim, A.H., 2014. A Batch-scheduling Problem to Minimize Total Actual Flow time of Parts through the Shop which Has m Heterogenous Batch Processors. In: Proceedings Asia Pacific Industrial Engineering and Management System, Jeju Island, South Korea

Hidayat, N.P.A., Cakravastia, A., Samadhi, T.M.A., Halim, A.H., 2016. A Batch Scheduling Model for m Heterogeneous Batch Processor. International Journal of Production Research, Volume 54(4), pp. 1170–1185

Hidayat, N.P.A., Cakravastia, A., Samadhi, T.M.A., Halim, A.H., 2018. Multi-Items Batch Scheduling Model for a Batch Processor to Minimize Total Actual Flow time of Parts through the Shop. Jurnal Teknik Industri, Volume 20(1), pp. 73-88

Liao, L.M., Huang, C.J., 2011. Tabu Search Heuristic for Two-Machine Flowshop with Batch Processing Machines. Computers & Industrial Engineering, Volume 60(3), pp.  426–432

Matin, H.N., Salmasi, N., Shahvari, O., 2017. Makespan Minimization in Flow Shop Batch Processing Problem with Different Batch Compositions on Machines. International Journal of Production Economics, Volume 193, pp. 832–844

Maulidya, R., Wangsaputra, R., Halim, A.H., 2020. A Batch Scheduling Model for a Three-stage Hybrid Flowshop Producing Product with Hierarchical Assembly Structures. International Journal of Technology, Volume 11(3), pp.608–618

Dauzère-Pérès, S., Mönch, L., 2013. Scheduling Jobs on a Single Batch Processing Machine with Incompatible Job Families and Weighted Number of Tardy Jobs Objective. Computers & Operations Research, Volume 40(5), pp. 1224–1233

Rossi, A., Puppato, A., Lanzetta, M., 2013. Heuristics for Scheduling A Two-Stage Hybrid Flow Shop with Parallel Batching Machines: Application at a Hospital Sterilisation Plant. International Journal of Production Research,  Volume 51(8), pp. 2363–2376

Surjandari, I., Rachman, A., Purdianta, D.A., Dhini, A., 2015. The Batch Scheduling Model For Dynamic Multi-Item, Multi-Level Production in an Assembly Job Shop with Parallel Machines. International Journal of Technology, Volume 1, pp. 84–96

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

Yusriski, R., Samadhi, T.M.A.A., Halim, A.H., 2016. An Integer Batch Scheduling Model for a Single Machine with Simultaneous Learning and Deterioration Effects to Minimize Total Actual Flow Time. In: IOP Conference Series: Materials Science and Engineering, Volume 114(1), p. 012073