A branch-and-price algorithm for robust parallel batch scheduling problem with uncertain size
| DOI | https://doi.org/10.1108/IMDS-12-2021-0807 |
| Published date | 23 May 2022 |
| Date | 23 May 2022 |
| Pages | 2351-2370 |
| Subject Matter | Information & knowledge management,Information systems,Data management systems,Knowledge management,Knowledge sharing,Management science & operations,Supply chain management,Supply chain information systems,Logistics,Quality management/systems |
| Author | Ting Wang,Xiaoling Shao,Xue Yan |
A branch-and-price algorithm for
robust parallel batch scheduling
problem with uncertain size
Ting Wang
School of Management Science and Engineering,
Nanjing University of Finance and Economics, Nanjing, China
Xiaoling Shao
School of Government Audit, Nanjing Audit University, Nanjing, China, and
Xue Yan
School of Finance, Nanjing Audit University, Nanjing, China
Abstract
Purpose –In intelligent scheduling, parallel batch processing can reasonably allocate production resources
and reduce the production cost per unit product. Hence, the research on a parallel batch scheduling problem
(PBSP) with uncertain job size is of great significance to realize the flexibility of product production and mass
customization of personalized products.
Design/methodology/approach –The authors propose a robust formulation in which the job size is defined
by budget constrained support. For obtaining the robust solution of the robust PBSP, the authors propose an
exact algorithm based on branch-and-price framework, where the pricing subproblem can be reduced to a
robust shortest path problem with resource constraints. The robust subproblem is transformed into a
deterministic mixed integer programming by duality. A series of deterministic shortest path problems with
resource constraints is derived from the programming for which the authors design an efficient label-setting
algorithm with a strong dominance rule.
Findings –The authors test the performance of the proposed algorithm on the extension of benchmark
instances in literature and compare the infeasible rate of robust and deterministic solutions in simulated
scenarios. The authors’results show the efficiency of the authors’algorithm and importance of incorporating
uncertainties in the problem.
Originality/value –This work is the first to study the PBSP with uncertain size. To solve this problem, the
authors design an efficient exact algorithm based on Dantzig–Wolfe decomposition. This can not only enrich
the intelligent manufacturing theory related to parallel batch scheduling but also provide ideas for relevant
enterprises to solve problems.
Keywords Intelligent scheduling, Robust optimization, Parallel batch scheduling, Uncertain size
Paper type Research paper
1. Introduction
With the development of mass customization, manufacturing enterprises need to obtain
customizinginformationand manufacturing datato realize the rationalallocation of production
resources (Frutos and Borenstein, 2004). Facing customers’pursuit of personalized products,
the modern manufacturing systemis gradually evolving to big dataand intelligence (Sanders,
2014).As intelligent equipment,the intelligent schedulingof manufacturingsystems can realize
the dynamic collaborative management of manufacturing enterprises by using artificial
intelligencetechnology (Fazel Zarandiet al., 2020). Therefore,optimizing intelligent scheduling
Optimizing
intelligent
scheduling
2351
The authors thank the anonymous reviewers whose constructive comments helped to improve the
original version of this paper. This research was supported by Young Foundation of Ministry of
education, humanities and social science research project (No: 20YJCZH203), the National Natural
Science Foundation of China (No: 72001112) and the Social Sciences Foundation of Jiangsu Province (No:
19EYB020).
The current issue and full text archive of this journal is available on Emerald Insight at:
https://www.emerald.com/insight/0263-5577.htm
Received 31 December 2021
Revised 14 March 2022
26 April 2022
Accepted 26 April 2022
Industrial Management & Data
Systems
Vol. 122 No. 10, 2022
pp. 2351-2370
© Emerald Publishing Limited
0263-5577
DOI 10.1108/IMDS-12-2021-0807
is the fundamentalway for enterprisesto quickly respond tomarket changes, organizeefficient
production and meetthe diversified needs of customers (Wang and Zhang, 2016).
Manufacturing systems usually have multiple parallel production lines or multiple
processes, and each process has multiple parallel equipment production (Koren and Shpitalni,
2010). Parallel batch scheduling can maximize the potential of the production line and reduce
the production cost of unit products through the reasonable allocation of production
resources (Pei et al., 2015). Hence, the parallel batch scheduling problem always is a research
hotspot in the field of intelligent scheduling. Although the functions of the equipment in the
parallel production line are the same, there are non-equivalent characteristics of different
processing capacity, different production times, and inconsistent production costs. In the
trend of customization, most research works mainly consider the parallel batch scheduling
problem of different jobs.
However, most of the related problems proposed are deterministic, that is, they are based
on nominal parameter values and do not consider uncertainty. In a real environment, various
sources of uncertainty in process scheduling can be identified, including not only the job-
related properties (e.g. processing time (Niu et al., 2019;Bruni et al., 2020;Zhang et al., 2018;
Wang et al., 2020b), due dates (Yue et al., 2020), setup time (Bruni et al., 2020) and machine-
related properties (e.g. maintenance time (Detti et al., 2019), machine breakdowns (Cai and Tu,
1996)). In addition, uncertain market trend is also an interfering factor (e.g. Cui and Engell,
2009;Bonfill et al., 2004).
The problemwe studied is motivatedby the project feasibilitystudy. The feasibilitystudy is
a scientific analysis of whether the project is technically and economically feasible before
investment decision-making (Shen et al.,2010). Among them, output prediction is the most
importantlink, which will be relatedto the scientificityof financial evaluation.For example, the
project unitswith a fixed number of personnelcan work on multiple projects atthe same time.
The numberof technical personnelrequired for each projectmay change due to some uncertain
factors. Because the project has an uncertain demand of personnel and the total number of
personnel of the project unit is limited, theoutput is often difficult to predict accurately. This
phenomenonis the most common in theevaluation of (Shen et al.,2010). The predictionscenario
in the project feasibility study can be abstracted into the uncertain PBSP model. Here, the
project corresponds to the job in the problem model, and all projects processed by the same
project unit form a batch in machine processing. There isn’t a feasible scheme if project
demands for personnel processed by the sameunit exceed their personnel limit.
In our work, we aim to investigate the parallel batch scheduling problem with uncertain
size. We consider a set of jobs. Each job has a certain processing time but with an uncertain
size. The uncertain job size is presented via budget constrained support. A subset of jobs that
can be processed simultaneously forms a batch require that the maximum of the total size
cannot exceed the limits of machine capacity. The processing time of each batch is
determined by the longest processing time of jobs in the batch. The problem is to arrange the
construction of the job batches to minimize the makespan, which is the completion time of the
last processed job in the schedule.
The remainder of this paper is organized as follows. Section 2 provides brief reviews of
deterministic PBSP and column-generation based algorithms to tackle variants of machine
scheduling under uncertainty. Section 3 presents the problem description and mathematical
formulation of R-PBSP with size uncertainty. In Section 4, we present in detail a branch-and-
price algorithm for the uncertain problem. Experimental design and results are then
discussed in Section 5. Finally, Conclusions are drawn in Section 6.
2. Related literature
In this section, we review the related literature from three aspects: (1) deterministic parallel
batch scheduling problem, (2) operational optimization problems under uncertain demand,
IMDS
122,10
2352
To continue reading
Request your trial