Source Codes, Input
& Solution Files for
I. K. Singgih, O. Yu, B.-I. Kim, J. Koo, and S. Lee ¡°Production Scheduling
Problem in a Factory of Automobile Component Primer Painting¡± working paper,
2019
1. Introduction
We study a
scheduling problem in a factory of automobile component primer painting, where
thousands of automobile parts undergo anti-corrosion electrodeposition coating.
The company uses a continuous hanger line. Component items are hung on hangers
and go through the painting (coating) steps. After coating, the component items
are wrapped at a packaging station.
All
component items undergo same painting processes in a pre-determined order, and
the conveyor line moves at a constant speed. Thus, the line productivity
depends on the hanger occupancy rate. An overhead hanger has a capacity limit
and can hold different numbers of items depending on the item type. Low hanger
occupancy rate and capacity loss will arise if the hanger capacity is not fully
utilized. To increase the hanger occupancy rate or utilization, the company
under study sometimes mixes two or more types of items on the same hangers, and
these are called mixed hangers. Placing mixed items on hangers increases
hanging workload for the coating process and additional setup time for the
packaging process. If mixing is necessary, then items with similar
characteristics must be hung on the same hangers to minimize the workload and
packaging setup time. The conflict between maximizing the hanger occupancy rate
and minimizing the number of mixed hangers and the dissimilarity of mixed items
on the same hangers should be considered, and the component items of an order
must be hung on consecutive hangers, such that the items of an order are
processed and packaged together.
The
workload in the packaging process must also be fully balanced during working
hours because the company employs different levels of packaging workforce
depending on the time of day. Different items require different workload
levels. At the packaging step, each item is manually packed in accordance with
its specification. Packing specifications can be categorized into three groups
depending on the workload. The packaging workload for several export items is
much higher than that for others. Given the continuous movement of the hanger
line, cumulative packaging workloads within a certain period or a certain
number of consecutive hangers should be fully balanced to avoid heavy fatigue
on workers at the packaging step.
The
problem can be stated as follows:
1. Input
(given data)
a. A set of items is given with the following
characteristics: code, amount, occupied hanger capacity, required number of
hangers per item, name, type code, sub-assembly name, car model, packing type,
packing load.
b. A set of hangers is given.
c. A set of eligibility restrictions between items and
hangers is given.
d. A set of mixing cost (penalty) between pairs of items
is given.
2. Output
(decision)
The amount of items hung and their
initial and final hanger numbers are determined.
3. Goal
(objective)
The
total capacity loss of the hangers (the remaining capacity on the hangers after
assigning items), total penalty for partially hung order items, total mixing
cost, and maximum workload of packing workers on consecutive numbers of hangers
must be minimized.
A mixed
integer programming (MIP) model for the scheduling problem is developed.
However, we cannot use the model for real-sized problems because it requires
extensive computation time due to its NP-hardness. Therefore, we develop a
2-Opt improvement algorithm and a tabu search metaheuristic algorithm. The MIP
model is solved using CPLEX 12.9.0, and the 2-Opt heuristic and tabu search
algorithms are implemented in C++ language using Microsoft Visual Studio 2010.
A solution
example is presented in Table 1. In the example, 36 of I4 items are hung on
hangers 1–6, 70 of I1 items are hung on hangers 7–20, and 32 of I3 items are
hung on hangers 23–30. The solution is represented with v = {I4, I1, I3, I2, I5}.
Table 1. A solution example
|
|
Hanger |
|||||||||||||||||||||||||||||
|
Item |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
|
4 |
6 |
6 |
6 |
6 |
6 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2. Experiments
In the
experiments, various numbers of hangers, such as 30, 200, 400, and 600, and
their corresponding working hours from 9:00 a.m. to 9:45 a.m., 12:00 p.m., 3:00
p.m., and 6:00 p.m., respectively, are tested. Instances with various numbers
of items (5, 30, 60, and 86) are also generated and solved. (In the real
situation, items with 86 types are hung onto 600 hangers). Table 2 shows the
summary of the data sets.
Table
2. Data sets
|
Data set |
No. of items |
No. of hangers |
|
1 |
5 |
30 |
|
2 |
30 |
30 |
|
3 |
60 |
30 |
|
4 |
86 |
30 |
|
5 |
86 |
200 |
|
6 |
86 |
400 |
|
7 |
86 |
600 |
Files for
the experiments can be downloaded below:
c.
Input data
(Please
locate all folders (a-d) above into a single folder.)