Abdul Hakim Halim, Nita Puspita Anugrawati Hidayat, Wisnu Aribowo

Corresponding email: nita.ph@gmail.com

Corresponding email: nita.ph@gmail.com

**Published at : ** 07 Oct 2022

**Volume :** **IJtech**
Vol 13, No 4 (2022)

**DOI :** https://doi.org/10.14716/ijtech.v13i4.4869

Halim, A.H., Hidayat, N.P.A., Aribowo, W., 2021. Single Item Batch-scheduling Model for a Flow Shop with m Batch-processing Machines to Minimize Total Actual Flow Time.

484

Abdul Hakim Halim | Department of Industrial Engineering, Bandung Institute of Technology, Jl. Ganesa 10 Bandung 40132, Indonesia |

Nita Puspita Anugrawati Hidayat | Department of Industrial Engineering, Bandung Islamic University, Jl. Tamansari no.1 Bandung 40132, Indonesia |

Wisnu Aribowo | Department of Industrial Engineering, Bandung Institute of Technology, Jl. Ganesa 10 Bandung 40132, Indonesia |

Abstract

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

Introduction

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.

Conclusion

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 *(N*)
is minimum when *N* equals the rounded-up value of *n- (N-*1) *c* and (*N*-1)
batches where the batch sizes are *c.* On the other hand, if *c*.
The solution in the scheduling subproblem will be minimum if the sequencing of *N*
resulting batches follows the Theorem; i.e., * i* = 2, 3,..., *N*
for *k* = 1,2,..., *m*, are determined referring to the ~~ ~~due dates.

Acknowledgement

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.

References

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