Research on game scheduling of galvanizing pipe production
In this paper, we analyze and integrate the production process of "hot-dip galvanized steel pipe", the main product in the case enterprise and builds a model for the production scheduling with Cooperative Game Theory from the perspective of the enterprise. In order to get the Optimal Game...
Saved in:
| Date: | 2017 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
НТК «Інститут монокристалів» НАН України
2017
|
| Series: | Functional Materials |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/136780 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Research on game scheduling of galvanizing pipe production / Yingying Li, Shaohua Dong // Functional Materials. — 2017. — Т. 24, № 3. — С. 490-495. — Бібліогр.: 11 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-136780 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1367802025-02-09T13:36:35Z Research on game scheduling of galvanizing pipe production Yingying Li Shaohua Dong Technology In this paper, we analyze and integrate the production process of "hot-dip galvanized steel pipe", the main product in the case enterprise and builds a model for the production scheduling with Cooperative Game Theory from the perspective of the enterprise. In order to get the Optimal Game Scheduling Solution, Genetic algorithm is used and Shaply value thought and β rule allocation method are combined to solve the problem of increased profit allocation in different customers. And fair and reasonable allocation mechanism is of great significance to the stability of the coalition and enterprise development. 2017 Article Research on game scheduling of galvanizing pipe production / Yingying Li, Shaohua Dong // Functional Materials. — 2017. — Т. 24, № 3. — С. 490-495. — Бібліогр.: 11 назв. — англ. 1027-5495 DOI: https://doi.org/10.15407/fm24.03.490 https://nasplib.isofts.kiev.ua/handle/123456789/136780 en Functional Materials application/pdf НТК «Інститут монокристалів» НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Technology Technology |
| spellingShingle |
Technology Technology Yingying Li Shaohua Dong Research on game scheduling of galvanizing pipe production Functional Materials |
| description |
In this paper, we analyze and integrate the production process of "hot-dip galvanized steel pipe", the main product in the case enterprise and builds a model for the production scheduling with Cooperative Game Theory from the perspective of the enterprise. In order to get the Optimal Game Scheduling Solution, Genetic algorithm is used and Shaply value thought and β rule allocation method are combined to solve the problem of increased profit allocation in different customers. And fair and reasonable allocation mechanism is of great significance to the stability of the coalition and enterprise development. |
| format |
Article |
| author |
Yingying Li Shaohua Dong |
| author_facet |
Yingying Li Shaohua Dong |
| author_sort |
Yingying Li |
| title |
Research on game scheduling of galvanizing pipe production |
| title_short |
Research on game scheduling of galvanizing pipe production |
| title_full |
Research on game scheduling of galvanizing pipe production |
| title_fullStr |
Research on game scheduling of galvanizing pipe production |
| title_full_unstemmed |
Research on game scheduling of galvanizing pipe production |
| title_sort |
research on game scheduling of galvanizing pipe production |
| publisher |
НТК «Інститут монокристалів» НАН України |
| publishDate |
2017 |
| topic_facet |
Technology |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/136780 |
| citation_txt |
Research on game scheduling of galvanizing pipe production / Yingying Li, Shaohua Dong // Functional Materials. — 2017. — Т. 24, № 3. — С. 490-495. — Бібліогр.: 11 назв. — англ. |
| series |
Functional Materials |
| work_keys_str_mv |
AT yingyingli researchongameschedulingofgalvanizingpipeproduction AT shaohuadong researchongameschedulingofgalvanizingpipeproduction |
| first_indexed |
2025-11-26T06:33:37Z |
| last_indexed |
2025-11-26T06:33:37Z |
| _version_ |
1849833629366091776 |
| fulltext |
490 Functional materials, 24, 3, 2017
ISSN 1027-5495. Functional Materials, 24, No.3 (2017), p. 490-495
doi:https://doi.org/10.15407/fm24.03.490 © 2017 — STC “Institute for Single Crystals”
Research on game scheduling of galvanizing pipe
production
Yingying �i�� �i���i�� Shaohua Dong
School of Mechanical Engineering, University of Science and Technology
Beijing, Beijing 100083, P.R. China
Received December 20, 2016
In this paper, we analyze and integrate the production process of “hot-dip galvanized steel
pipe”, the main product in the case enterprise and builds a model for the production scheduling
with Cooperative Game Theory from the perspective of the enterprise. In order to get the Opti-
mal Game Scheduling Solution, Genetic algorithm is used and Shaply value thought and β rule
allocation method are combined to solve the problem of increased profit allocation in different
customers. And fair and reasonable allocation mechanism is of great significance to the stability
of the coalition and enterprise development.
Keywords:� Galvanizing Pipe Production, Cooperative Game Theory, Genetic algorithm.
Проанализирован процесс производства горячеоцинкованных стальных труб, основного
продукта предприятия, построена модель планирования производства при помощи
кооперативной теории игр с точки зрения предприятия. Чтобы получить оптимальное
решение используется генетический алгоритм. Метод построения значений Shaply и метод
распределения правил β объединяются для решения проблемы увеличения распределения
прибыли у разных клиентов, что имеет большое значение для стабильности развития
предприятий.
Дослідження питань виробництва гальванічних труб Yingying Li, Shaohua Dong
Проаналізовано процес виробництва гарячеоцинкованим сталевих труб, основного
продукту підприємства, побудована модель планування виробництва за допомогою
кооперативної теорії ігор з точки зору підприємства. Щоб отримати оптимальне рішення
використовується генетичний алгоритм. Метод побудови значень Shaply і метод розподілу
правил β об’єднуються для вирішення проблеми збільшення розподілу прибутку у різних
клієнтів, що має велике значення для стабільності розвитку підприємств.
1. ������������������������
The concept of computer integrated
manufacturing system (CIMS) is put forward
by Dr. Joseph Harrington firstly in 1973. Pro-
duction scheduling technology is one of key and
core technologies of CIMS [1]. Production sched-
uling has been widely concerned because of its
important place in enterprise production man-
agement in recent decades. Experts and schol-
ars in the field of production scheduling have
proposed a series of research methods to solve
all kinds of production scheduling problems.
Such as some traditional scheduling methods
(e.g. mechanical optimization method, simula-
tion method) and intelligent scheduling meth-
ods (e.g. genetic algorithm, swarm intelligence
algorithm, neural network algorithm). These
methods have achieved good results in the field
of production management, and have made
contributions to raising the level of production
management. The Game Theory proposed and
developed in the middle of 20th century is main-
ly used to solve the problem of interests balance
between enterprises and customers and among
multiple customers. Meanwhile, the production
Functional materials, 24, 3, 2017 491
Yingying Li, Shaohua Dong / Research on game scheduling of ...
scheduling is a typical problem of resource al-
location and competition with constraints and
optimization index requirements where there
are a lot of conflicts among customers, custom-
ers and enterprises. Therefore Game Theory
has become a good tool to describe the schedul-
ing problem. The game is generally divided into
non-cooperative game and cooperative game.
Non-cooperative game highlights the concept
of individual competition, emphasizing the in-
dividual rationality, while in the cooperative
game, the agents can reach a binding agree-
ment to carry out a coalition. Cooperative game
embodies the spirit of teamwork, emphasizing
the collective rationality.
Tijs (1986) used the cooperative game the-
ory to solve the problem of cost saving in pro-
duction scheduling, and proposed the cost dif-
ference allocation method based on τ value in
the scheduling problem[2]. Curiel et al. (1989)
started a line of research that investigates the
interaction between sequencing situations and
cooperative games. They considered the class of
one-machine sequencing situations in which no
restrictions like due dates and ready times are
imposed on the jobs and the weighted comple-
tion time was chosen as the cost criterion [3].
Zhou (2012) allocated saving costs reasonably
by cooperation theory in the game of one-ma-
chine scheduling with due-date and tardiness
penalty[4].
In the literature review of the game sched-
uling problems are standing in the customers’
point of view, however in this paper, the pro-
duction process of a steel pipe enterprise’s main
product “Hot dip galvanized steel pipe” is as an
example to study, in which we analyze the con-
tribution of customers to increasing the profit
of the case enterprise with cooperative game
theory to help to adjust customer strategy ac-
cordingly.
2. C��pe�a��ve game m��el �f galva-
��z��g p�pe p���������
The galvanizing process is classified and
integrated in consideration of the actual situ-
ation in the enterprise. Integrated galvanizing
process is displayed in Table 1. Taking full ac-
count of the properties of the works, the inte-
grated galvanizing process is considered as a
single machine model. Before modeling, the as-
sumptions are as follows:
1. Ade�uate supply of raw materials is as�Adequate supply of raw materials is as-ate supply of raw materials is as-
sured;
2. Customers’ payment of accepting the co-
alition is not more than the payment of reject-
ing the coalition;
3. Each galvanizing task belongs to only one
customer;
4. Galvanizing tasks arrive at the same
time. There is no waiting time;no waiting time;
5. The enterprise provides an initial sched-
uling order before the beginning of galvanizing
with a view to the due dates and the weight
of the customers. Under the initial order, once
the delivery time of one task exceeds the due
date, the task will be rejected, and the profit
that this task brings to the enterprise is 0 si-
multaneously;
6. If one customer accepts the coalition, the
delivery time of each task of this customer in
the coalition is allowed to be later than the due
date, but not later than the deadline. If not, the
profit of the task is 0;
7. The machine can only carry out one task at
the same time. The task can be neither stopped
early nor preempted by other tasks;
8. The time of starting galvanizing is 0.anizing is 0.
Based on the above assumptions, the
mathematical model of galvanizing pro-
duction scheduling problem is given. The
problem can be described as an eight tuple
( , , , , , , , )N l T R ED LD Fσ0 . N represents the set
of galvanizing tasks, in which galvanizing tasks
are called agents.. l, the machine set, is set to
1 in the model. R is defined as galvanizing time
set.σ0, a sort of N is seen as initial schedul-
ing order from the enterprise. ED and LD are
due-dates set and deadlines set, respectively.
F i( ) is to be interpreted as the penalty function
when the delivery time of i-th task is between
ED i( ) and LD i( ) . According to the customers’
orders, the profit that the enterprise get from
productions and sales is defined as follows:
U Ri
' =å (1)(1)
R q p c Fi i i i i= ´ - -( ) (2)(2)
Table 1. Integrated Galvanizing Process
Serial Number Process Name Process Description
1 Pickling Picking ,washing and drying pipes
2 Galvanizing Galvanizing the pipes in zinc liquid
3 Passivation Drying the galvanized pipes and spreading the passivator
on the pipe surface
492 Functional materials, 24, 3, 2017
Yingying Li, Shaohua Dong / Research on game scheduling of ...
F f T EDi i i i= ´ -( ) (3)(3)
where for all i N p c qi i iÎ , , , and fi are repre-
sented the unit price , the quantity, the penalty
of i-th specification galvanized pipe respec-
tively. Given the initial orderσ0,we have the
initial profit of the enterprise:
U q p ci i i0 = ´ -å ' ( ) (4)(4)
q
q T ED
T EDi
i i i
i i
' ,
,
=
- £
- >
ì
í
ïï
îïï
0
0 0
(5) (5)
where if the delivery time of i-th task exceeds
the due date, the quantity qi
' is 0, otherwise
is qi . In the cooperative gaming, the increased
profit after re�order is given:
U U U= -max( )'
0 (6)(6)
The ultimate goal of the cooperative game
model in this paper is to maximize the in-
creased value of enterprise profit. Since the
enterprise profits under the initial order σ0
can be calculated, the goal of cooperative game
model is transformed into maximizing the value
of U' . When satisfying the following constraints
and making U' max, the scheduling solution is
called the optimal game scheduling solution for
the galvanized production in this model:
T LD i ni i- £ = ×××0 1 2, , , , (7) (7)
The profit each task contributes in the coali-
tion will be analyzed in detail in section 4. Heu-
ristic genetic algorithm will be used to solve the
cooperative game model in the next section for
improving convergence speed.
3. S�lv��g �he ���pe�a��ve game m��el
�f galva��z��g p�pe p���������
The previous section we introduced the prob-
lem of galvanizing production scheduling and
used the cooperative game theory to establish
a cooperative game scheduling model based on
the maximization of enterprise’s profit. In this
section we will use the genetic algorithm to
solve the model, and provide method support
for the allocation of profit in the next section.
The genetic algorithm flow is as follows:
(1) Coding design
Firstly, the model is coded according to
the following rule: the Galvanizing tasks of n
specifications are se�uential encoded from 1 to
n under the initial order of σ0 .A chromosome
containing n genes is obtained.
(2) Fitness function design
The goal of the cooperative game model
established in the previous section is to maxi-
mize the profit of the enterprise. Therefore, the
maximumU g
max
' and minimum U g
min
' are selected
in the g-th generation to compose the fitness
function:
fitness i
U U
U U
i
g g
g g
c( ) (
.
)
'
min
'
max
'
min
'
=
-
- + 0 001
(8)(8)
where Ui
g' is the enterprise’s profit under the i
order in the g-th generation, and c is the nor-
malized phase-out acceleration index.
Table 2. Example Order Information
Task
Num-
ber
Cus-
tomer
Number
Specifications Weight, t Unit Cost,
Yuan/t
Unit Price,
Yuan/t
Due- date,
h
Deadline,
h
Penalty Cost,
Yuan/h
1 1 114.0´3.75´6.0 341.73 2894.87 2965.90 103.80 186.84 122.06
2 1 140.0´4.0´6.0 33.73 2944.36 3188.00 98.95 148.43 21.73
3 1 26.3´2.5´6.0 38.25 2866.56 3502.39 54.75 87.60 40.79
4 2 33.5´3.25´6.0 27.52 2758.90 3290.02 52.64 73.69 43.01
5 2 42.0´2.75´6.0 120.81 2851.03 3323.17 89.71 116.63 149.17
6 2 42.0´3.0´6.0 139.90 2673.58 3278.43 102.32 133.02 149.41
7 2 47.0´2.5´6.0 26.16 2854.97 3332.50 85.89 154.61 12.69
8 3 47.5´3.0´6.0 117.60 2752.20 3258.46 86.65 155.98 55.28
9 3 47.5´3.25´6.0 46.73 2841.91 3213.75 97.57 175.62 19.24
10 4 75.0´3.0´6.0 24.83 3029.24 3060.01 87.33 157.19 10.88
11 4 75.0´3.25´6.0 85.54 2950.75 3000.58 91.32 164.37 35.13
12 4 75.0´3.5´6.0 118.79 2859.98 2969.51 93.80 150.08 62.67
13 4 114.0´3.25´6.0 45.54 3002.84 3041.34 84.19 115.91 43.66
14 5 114.0´3.5´6.0 331.63 2958.61 2994.19 128.28 177.57 201.44
Functional materials, 24, 3, 2017 493
Yingying Li, Shaohua Dong / Research on game scheduling of ...
(3) Selection, Crossover and Mutation Op-
erator
The roulette method is chosen to generate
the selection operator. The crossover operator
uses a single point of crossover. The mutation
operator is obtained by comparing the random
probability with the mutation probability Pm
.When the random probability is less than Pm
, the random number method is used to gener-
ate a task number to replace the existing task
number of the gene.
(4) Algorithm Flow
Based on the above analysis of significant
steps of genetic algorithm, the genetic algo-
rithm flow is given in Fig.1.
In order to verify the rationality and
correctness of the galvanization cooperative
game model in the previous section and the so-
lution designed in this section, in this paper,
we use Matlab software to simulate the experi-
ment. In the experiment, we integrate multiple
production lines into a production line in the
galvanizing workshop, and 14 kinds of specifi-
cations need to be galvanized after integrating
and classifying the customer orders. Table 2
shows the example order information. The ex-
perimental parameters are set as follows: the
population is 100, the number of generations is
200, normalized phase-out acceleration index is
set to be 2, crossover probability is 0.75 and the
mutation probability is 0.2.
According to the above genetic algorithm
parameters settings and order information, ge-
netic algorithm simulation convergence curve is
shown in Fig. 2. With the combination of the max-
imum profit of the enterpriseU' .= 325009 50
and the profit in the initial scheduling order
U0 254753 60= . , the increase of enterprise profit
is U=70255 90. and rises 27.6%.
It can be seen from the simulation results
that the profit from the optimized production
scheduling order is considerably higher than
from the initial order. As the promotion of
profit is based on the customer coalition, it is
important to study which customers join in the
coalition and the contribution of each customer
in the coalition for adjusting the customer re-
lationship management strategy. In the next
section, we will focus on the analysis of the
coalition’s profit allocation.
4. Galva��ze� p��������� game ��al�-
tion profit allocation
After obtaining the optimal scheduling solu-
tion of the cooperative game model, it is neces-
sary to allocate the profit rationally. A reason-
able allocation mechanism is of great signifi-
cance to the stability of the coalition. All of the
contributors in the coalition can benefit from
the allocation. The profit allocation mechanism
should apply the following rules:
(1) Collective Principle
Under the optimal cooperative game sched-
uling σ b the total profit is not less than the to-
tal profit under other scheduling, that is, the
optimal cooperative game scheduling solution
can maximize the profit. Meanwhile, the profit
margin must be fully allocated among all of the
participating agents, and there is no surplus.
Fig. 1. Genetic algorithm flow chart
Fig. 2. Genetic algorithm simulation conver-
gence curve
494 Functional materials, 24, 3, 2017
Yingying Li, Shaohua Dong / Research on game scheduling of ...
(2) Individual Rationality Principle
The cost savings of the customer after joining
the coalition must be nonnegative, which is the
prerequisite for the formation of the coalition.
And the relevant assumptions have been made
in the cooperative game model in this paper.
(3) No Damage Principle
When the customers in the coalition is part
of the all customers, the interests of non�affili-
ated customers can’t be damaged.
(4) Fairness Principle
The fairness and reasonability are reflected
in the following the allocation strategy: The
more contribution the customers make, the
more profit they should be allocated, and the
customer who makes no contribution can’t par-
ticipate in the allocation of profits.
According to the above principles and the
situation of the enterprise, this paper will in-
troduce two kinds of key cooperative game allo-
cation methods: Shapley value method and β
rule allocation method.
(1) Shapley Value
The Shapley value proposed by Shapley
in 1953 solved the allocation in the coopera-
tive game reasonably and fairly. The status of
Sharply value in cooperative game is equiva-
lent to the status of Nash equilibrium in non-
cooperative game. The main ideas of Sharply
value are described as follows:
It is assumed that agents in the cooperative
game can form a perfect coalition, and the num-
ber order of agents in the game isorder of agents in the game is ( , ,..., ),1 2 n
we get:
x v1 1= ({ })
x v v2 1 2 1= -({ , }) ({ })
x v v3 1 2 3 1 2= -({ , , }) ({ , })
x v N v N nn = -({ }) ( ,{ })
It leads to an allocation of x x x xn= ( , , , ),1 2
which is related to the number of agents in the
coalition. Reassigning the number of the agents
in the coalition, we will receive another alloca-
tion under this numbering. With any numbering
mode, the income of each agent can be obtained
by getting the difference between the income of
the coalition after the agent joined and before
he joined. And the number of numbering modes
is n ! in a coalition with n agents. Therefore,
when defining the coalition after agent i joined
as M iÈ { } , the incomeϕi v( ) that i should be al-
located is the average of incomes he got in n !
allocations [5]:
ϕi v
M N M
N
v M i v M
M N i
( )
| | !(| | | | ) !
| | !
[ ( { }) ( )]
{ }
=
- -
È -
Ì -
å 1
(9)(9)
ϕi
M N i
v W M v M i v M( ) ( )[ ( { }) ( )]
{ }
= È -
Ì -
å (10)(10)
(2) β rule allocation method
The β rule allocation method is a allocation
method proposed by Curiel[3] in studying se-
�uence game. Above all, we define several sets
about order σ0 :
P i( , )σ0 : the set of agents in front of i
P i( , )σ0 : the set of agents in front of i add-
ing i
F i( , )σ0 : the set of agents behind of i
F i( , )σ0 : the set of agents behind of i add-
ing i
The income of i -th agent is derived from the
following formula:
β
σ σ σ σ
i v
P i P i F i F i
( )
[ ( , ) ( , ) ( , ) ( , )]
=
= - + -
1
2 0 0 0 0
(11)(11)
It can be seen from the above formula that
the income obtained by each agent i is the aver-
age of the marginal revenue value obtained by
adding i to the coalition in front of i and add-
ing to the coalition behind i .
Weighted marginal cost allocate rule on pre-
decessors and followers (WMCA), the alloca-
tion method combined by above two methods,
is used in this paper and defined as follows:
β λ σ σ
λ σ σ
i v P i P i
F i F i
( ) [ ( , ) ( , )]
( )[ ( , ) ( , )]
= - +
+ - -
0 0
0 01
(12)
where λ is the weighting coefficient, and
λ Î [ , ]0 1 . The value of λ reflects the urgency
of the agent’s re�uest for advance processing.
In the previous section, the total profit of
the enterprise under the initial order and the
optimal game scheduling order based on Table
2 have been obtained. Since the different galva-
nizing tasks belong to different customers, the
total contribution of each customer is the sum
of the contributions of the customer’s galvaniz-
ing tasks. The profit the enterprise get from all
of the connected task coalitions are shown in
Table 3.
In the light of the Formula(12), Table 4 dis-
played the contributions of different galvaniz-
ing tasks by taking the λ = 0.6. From the results
of the allocation, we can see from the results of
the allocation that the tasks numbered 2,3,4,5
have no contribution to the promotion of profit,
which implies the change of processing order of
this four tasks has no effect on the profit pro-
Functional materials, 24, 3, 2017 495
Yingying Li, Shaohua Dong / Research on game scheduling of ...
motion. And this statement is confirmed in the
reality of that there is no change of the order of
this 4 tasks in optimal game scheduling order
[13,2,3,4,5,7,12,11,10,8,6,14,9,1].
The total sum of customers’ contributions is
70255.90 Yuan, that is, all of the profit alloca-
tion is completed.
5. C���l�s���s
In this paper, we take the production pro-
cess of the main product “hot-dip galvanized
steel pipe” in the case enterprise as a research
object and analyze the contribution of each
customer to the improvement of the enterprise
profit with cooperative game theory, which is of
great significance to the stability of the coali-
tion and the development of the enterprise. For
the tasks of non-expired, their contributed prof-
it can be all owned by the enterprise, while for
the tasks of overdue, the enterprise can make
compensation for the corresponding customers,
which help the enterprise retain customers in
the environment with steel-making overcapac-
ity currently.
Refe�e��es
1. Weiss, Gideon, Michael Pinedo, Interfaces, 25,
130, 1995.
2. Tijs S H and Driessen T S H, Manag. Scien., 32,
1015, 1986.
3. Curiel I, Pederzoli G, Tijs S, Eur. J.Oper.Res, 40,
344, 1989.
4. Zhou Y P, Gu X S,, CIESC J.,61, 1983, 2010.
5. Hongkuan Ma, Game theory. Shanghai: Tongji
University press, pp. 152�161, 2015.
6. Gupta M, Mohanty B K, Comp. Industr. Eng.,
87, 454, 2015.
7. Feldmann M and Biskup D, Comp. Industr.Eng.,
44, 307, 2003.
8. Hamers H, Klijn F and Suijs J,, Eur. J. Oper.
Res, 119, 678, 1999.
9. Borm P, Fiestras�Janeiro G, Hamers H, et al, ,
Eur. J.Oper.Res., 136, 616, 2002.
10. Gerichhausen M, Hamers H. Partitioning, Eur.
J. Oper.Res, 196, 207, 2009.
11. Van Velzen B, Eur. J.Oper.Res, 172, 64, 2006.
|