Flow Shop Scheduling Problem with Convex Resource Allocation and Learning Effect ()
1. Introduction
In the scheduling problem of industrial production, the processing of the job is complicated. The processing time of the job in the classic scheduling problem is a constant, but in the actual production, the actual processing time of the job is often related to the normal processing time of the job, allocation of resources, learning effects, deteriorating effects of the machine and other factors. In view of the complexity of the current scheduling problem, a large number of scholars have given their own research. In 1980, Vickson [1] first proposed that the processing time has the resources controllable problem, which broke through the classic model of the scheduling problem and brought new research directions in the scheduling field. In actual industrial production, managers often use non-renewable resources as a tool to control the processing time of the job, so as to improve the running effect of the system. The scheduling problem of resource-constrained processing time has also attracted the attention of scholars. In actual industrial production, with the improvement of worker's proficiency and the shorter machining time of the job, Biskup [2] first proposed a scheduling problem with learning effect, and gave a new model. Wang et al. [3] studied the single machine scheduling problems with learning effects and resource allocation, and obtained the optimal schedule, resource allocation and optimal algorithm. Shabaty and Kaspi [4] proposed scheduling problems with convex resource-dependent processing times, and discussed the single-machine problems with the minimization of the total weighted flow time. Since then, Leyvand et al. [5] have proposed and demonstrated a uniform approach to scheduling problems with convex resource allocation. Zhu et al. [6] studied group scheduling problem with learning effect and resource allocation on a single-machine. Wang and Wang [7] studied the single machine scheduling problem with learning effect and convex resource-dependent processing time. Liu et al. [8] studied two-machine scheduling problem with learning effect and convex resource processing time under common due date, and gave the optimal algorithm to prove that it is solvable in polynomial time. Lu et al. [9] considered the optimal due-date assignment problem with learning effect and resource-dependent processing times. Li et al. [10] studied a single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation. Yin et al. [11] studied a single machine scheduling problem with learning effects and controllable processing time. Gao et al. [12] considered two-machine no-wait flow shop scheduling problem with learning effect and convex resource allocation. Under the common due date condition, they proved the problem can be solved in polynomial time.
In this paper, we consider the two-machine no-wait flow shop scheduling problem with learning effects and convex resource allocation. Under limited resource availability, some results are given.
2. Problem Formulation
There are
independent jobs
to be processed on a two-machine flow shop setting. Each job is required to be processed on machine
and then on machine
, and between the two machines, the jobs are not allowed to wait, the operation
(
). The processing time of each job is give as follows:
(1)
where
is the actual processing time of operation
,
is the normal processing time of operation
,
represents the amount of a non-renewable resource allocated to operation
,
is the actual scheduling position of the job
,
is the learning index(
),
is a positive constant.
In this model,
is the common due date,
is the completion time of job
,
is the earliness of job
,
is the tardiness of job
. The purpose is to determine the optimal schedule
, the optimal resource allocation strategy
, and
the common due date
of jobs under the condition
so that the following objective function is minimized:
(2)
where weights
are given constants (
). In what follows, the problem studied will be denoted by using the extended three-field notation scheme (Graham et al. [13]).
3. Main Results
Lemma 1. (Gao et al. [12]) For any specified schedule
, there exists an optimal common due date with the property that the common due date value
coincides with the completion time of a job.
Lemma 2. (Gao et al. [12]) For the
problem, an optimal sequence exists such that
, where
(3)
As in Gao et al. [12], for a no-wait flow shop problem with a constraint
, we have
(4)
where
(5)
and
(6)
Lemma 3. For a given sequence
, the optimal resource allocation
for the problem
is:
(7)
(8)
Proof. Obviously under the condition
, we can get the minimum value of the objective function.
Min
S.t.
(9)
According to Lagrangian multiplier method, from (9) and (4), we have:
(10)
where
is the Lagrangian multiplier.
Since each of the objectives is a convex function, according to Lagrangian multiplier method.
Differentiating (10) with respect to
, we have
(11)
then
(12)
Differentiating (10) with respect to
, we have
(13)
then
(14)
Differentiating (10) with respect to
, we have
(15)
Substituting (12) and (14) into (15), we have
(16)
From (16) and (12), we have
From (16) and (14), we have
Substituting (7) and (8) into (4), under optimal resource allocation
and
, we obtain that a new unified expression for
.
(17)
In what follows, we derive the optimal schedule for
It is clear that the minimum value of (17) is equal to minimizing
Let us define binary variables
, such that
, if job
is scheduled at position
, otherwise
. Then, the problem
can be solved by the following linear assignment problem:
Min
(18)
S.t.
(19)
(20)
(21)
where
(22)
(23)
and
(24)
By solving this linear assignment problem, we can get the optimal job sequence
of the problem
Based on the above analysis, our algorithm for
can be described as follows.
Algorithm 1
Step 1. According to (3), calculate
.
Step 2. According to (22), calculate the
.
Step 3. Solve the linear assignment problem (18)-(21) to determine the optimal job sequence
.
Step 4. According to (7) and (8), calculate the optimal resource allocation
.
Step 5. According to (1), calculate the actual processing times
.
Step 6. Calculate the common due date
.
Theorem 1. The problem
can be solved in
time by Algorithm 1.
Proof. According to the lemmas 1, 2, 3 and the assignment problem (18)-(21), we can get the correctness of Algorithm 1, the complexity of step 2 in Algorithm 1 is
, step 3 is
, the complexity of steps 1,4,5,6 is
. So the complexity of Algorithm 1 is
.
Acknowledgements
Hsu was supported by the Ministry Science and Technology of Taiwan under Grant MOST 106-2221-E-252-003.