Cheng Wang* | Lei Zeng
OPEN ACCESS
Job-shop production often faces many uncertainties arising from the interaction between various resources. The schedule must be robust enough to ensure smooth production under the uncertain environment. In this paper, the multi-objective job-shop scheduling problem (JSP) is optimized based on the tradeoff between time, cost and robustness. Firstly, a multi-objective optimization model was constructed, and the tradeoffs between three objectives, namely, time, cost and robustness, were discussed in details. After that, a genetic algorithm (GA) coupling non-dominated ranking was designed to solve the multi-objective JSP. Finally, the proposed model was verified using an example of JSP and the objective tradeoffs were validated through sensitivity analysis. The research findings shed important new light on multi-objective JSP under various constraints.
job-shop scheduling problem (JSP), multi-objective tradeoff, optimization model, uncertain environment
Many manufacturing enterprises have a limited amount of resources. During production, these resources continue to fluctuate and interact with each other, bottlenecking the effective output of job-shops, the basic units of production activities. To solve the bottleneck, it is necessary to optimize the production process through rational planning of time and resources, that is, solve the job-shop scheduling problem (JSP) [1-2].
Job-shop scheduling should fully rationalize job sequencing based on urgency and allocate resources to minimize waste. The resulting schedule must be executed strictly by job-shops. The JSP is a very complex combinatorial optimization problem [3], because various production factors need to be considered, namely, the arrival time, processing time and load of resources.
In reality, the production process is often disturbed by uncertainties like rework and machine failure. These uncertain factors must be taken into account in job-shop scheduling. Under the given resources and duration limit, the time, cost and robustness of the schedule are deeply correlated and highly interactive. All the three indices should be optimized simultaneously in job-shop scheduling, in the case that the optimization of a single index may undermine that of the other indices.
This paper explores the multi-objective JSP based on the tradeoff between time, cost and robustness in uncertain environment. Under the constraints of renewable resources, the start time of each process was determined, and the schedule was prepared to achieve the optimal time, cost and robustness.
In the early 1950s, Johnson et al. [6] set up an objective function for two-machine scheduling, inspiring a wave of research on the JSP. Considering the complexity of job-shop scheduling, many simple rules have been developed through mathematical and physical methods (e.g. integer programming, branch definition and dynamic programming in operational research) for theoretical derivation of the optimal schedules. Helal et al. [7] proved that, in most cases, the JSP is a non-deterministic polynomial-time (NP) hard problem. In other words, the optimal solution cannot be obtained by polynomial time method, even if the problem is on a small scale. To overcome the NP-hardness, several advanced algorithms have been applied, either separately or in hybrid form, to largescale JSPs, including neural network, genetic algorithm (GA), simulated annealing (SA) and chaos algorithm. For example, Wang et al. [8] established an adaptive rescheduling method for flexible job-shop based on the advanced GA. Yan et al. [9] designed a GA to create the job-shop scheduling model and algorithm for complex job-shop scheduling.
Since job-shop scheduling is fundamentally multi-objective, the tradeoff between multiple objectives has attracted a growing attention [10]. For example, Demeulemeester et al. [11] studied the discrete time/cost tradeoff problem in deterministic environments and solved it by an exact algorithm. Wiesemann et al. [12] described the relationship between time and cost by nonlinear function, and examined the continuous time/cost tradeoff problem. Erenguc et al. [13] explored the resource-constrained time/cost tradeoff problem under multi-mode conditions, adopted the branch-and-bound algorithm to solve the problem, and verified the method with an example. Based on decomposition strategy, Deirmenci [14] et al. employed precise algorithm to minimize the completion time in discrete-time/cost tradeoff of largescale JSPs.
Recent years saw a rising research interests in multi-objective tradeoff under uncertain environment. For instance, Lei et al. [15] studied the tradeoff between time and robustness under resource constraint. Mazidi et al. [16] constructed a time/cost tradeoff model under stochastic environment and solved it with hybrid intelligent optimization algorithm. Hao et al. [17] created a robust scheduling mechanism, constructed an optimization model for the minimal time and maximal robustness, and solved the model with heuristic algorithm. With the aid of the GA, Qi et al. [18] optimized the production robustness under uncertain time, and effectively overcame the random differences caused by uncertain time. Gomes et al. [19] transformed the fuzzy multi-objective resource constrained scheduling problem into a single-objective combinatorial optimization problem, and obtained a set of effective solutions by genetic local search algorithm. Chen et al. [20] constructed a mathematic model to prepare the benchmark schedule in a specific production environment, and measured scheduling stability through the weighting of the deviation between expected and actual schedules.
3.1 Problem definition
The production task in job-shop can be expressed as an activity-on-node network G=(V,A) [21], where V={0,1,2,...,n,n+1} is the set of nodes (jobs) and A is the set of directed arcs (logical relations between the jobs). Each job starts immediately after the completion of the previous job. Two virtual jobs 0 and n+1 were added to represent the start and end of the production task. The two jobs have a time length of zero and occupy no resource.
Let B be the number of renewable resources and D be the maximum duration of the production task. For resource k, the availability per unit time is denoted as Bk, and the occupancy cost per unit time as ck. For job i, the start time is denoted as Si, the processing duration as di, the demand for resource k as rik, and the delay cost per unit time as wi.
The start time of job i was taken as the decision variable of the JSP. After all, the first step to prepare a feasible schedule is to determine the start time of each job under such constraints as the job sequence. In actual job-shop scheduling, a buffer time is usually arranged between jobs to minimize the impact of uncertainties on the production process, making the schedule more robust against interference. The addition of buffer time enhances the flexibility of the start time of jobs.
In this paper, the concept of free time difference (FTD) is introduced to measure the buffer time. This concept refers to the interval for the start time of the current job under the resource constraint, which does not affect the earliest start time of the subsequent jobs. The FTD of job i (∆i) can be defined as:
$\Delta _ { i } = \min _ { j \in S u c c _ { i } } \left( s _ { i } - d _ { i } \right) - s _ { i } , \quad i = 0,1 , \ldots , n$
where Succi is the set of subsequent jobs for job i. For job i, the subsequent jobs will not be affected, as long as the delay caused by uncertainties falls within the FTD. If the delay surpasses the FTD, the subsequent jobs will be delayed, incurring a delay cost.
As mentioned before, the FTD helps to enhance schedule robustness. But the enhancement per unit of FTD varies from job to job. To measure the variation, the cumulative instability weight (CIW) was adopted to determine the weight of each job. The CIW of job i (CIWi) can be defined as:
$C I W _ { i } = w _ { i } + \sum _ { j \in S u c c _ { i } } w _ { j } , \quad i = 0,1 , \ldots , n$
The greater the CIWi, the higher the production loss induced by the delay of job i.
For the three objectives of the JSP, the completion time of the production task was expressed by the start time of the virtual job n+1, and defined as T=Sn+1; the schedule robustness was represented as the weighted total FTD of all jobs, and defined as $R = \sum _ { i = 1 } ^ { n } \left( C I W _ { i } \times \Delta _ { i } \right)$; the production cost was described as all renewable resources occupied by jobs, and defined as $C = \sum _ { i = 1 } ^ { n } \sum _ { k = 1 } ^ { K } c _ { k } \times \left( d _ { i } + \Delta _ { i } \right) \times r _ { i k }$.
Considering the interaction between the T, R and C, this paper makes tradeoffs between the three objectives, and attempts to minimize T and C and maximize R simultaneously under the given conditions.
3.2 Model optimization
In the light of our JSP, the multi-objective optimization model was constructed as:
$\min T = s _ { n + 1 }$ (1)
$\max R = \sum _ { i = 1 } ^ { n } \left( C I W _ { i } \times \Delta _ { i } \right)$ (2)
$\min C = \sum _ { i = 1 } ^ { n } \sum _ { k = 1 } ^ { K } c _ { k } \times \left( d _ { i } + \Delta _ { i } \right) \times r _ { i k }$ (3)
s. t. $\sum _ { i \in V ^ { t } } r _ { i k } \leq R _ { k } , t = 1,2 , \ldots , D , k = 1,2 , \ldots , K$ (4)
$s _ { i } + d _ { i } \leq s _ { j } , j \in S u c c _ { i } , i = 1,2 , \ldots , n$ (5)
$\Delta _ { i } = \min _ { j \in S u c c _ { i } } \left( s _ { i } - d _ { i } \right) - s _ { i } , \quad i = 0,1 , \ldots , n$ (6)
where Vt is the set of jobs being processed at time t.
Equations (1)~(3) are the three objectives of our JSP and Equations (4) and (5) are the two constraints of the problem. Specifically, Equation (1) represents the minimization of the production duration, i.e. the start time Sn+1 of the virtual job n+1; Equation (2) means the maximization of schedule robustness, i.e. the total FTD weight of all jobs; Equation (3) indicates the minimization of production cost, i.e. all renewable resources occupied by jobs; Equation (4) requires that the amount of occupied resources should not exceed the amount of available resources; Equation (5) specifies that a job must be processed immediately after the completion of the previous job. In addition, Equation (6) provides the way to compute the FTD based on the start time of jobs.
According to the establish model, a schedule for the production task can be prepared after determining the start time si of each job. Each schedule has a fixed time, robustness and cost. The values of these three objectives can be adjusted by changing the decision variable, i.e. the start time. The three objectives can be optimized simultaneously through repeated comparison and weighing between different schedules.
3.3 Objective tradeoffs
Our multi-objective optimization model was divided into three parts for in-depth discussion. The three parts are the time-constrained tradeoff between robustness and cost, the robustness-constrained tradeoff between time and cost, and the cost-constrained tradeoff between time and robustness.
(1) Time-constrained robustness/cost tradeoff
The sub-model of the time-constrained robustness/cost tradeoff can be obtained, after transforming the time objective function of our model into a constraint:
s. t. $s _ { n + 1 } \leq D ^ { * }$ (7)
where D* is the given maximum duration of the production task.
Since the time function has been transformed into a constraint, the sub-model has two objective functions, respectively for cost and robustness. It can be seen from the two functions that both robustness and cost contain the FTD ∆i, which depends on the start time si. The FTD of each job can be adjusted by changing the start time and the task duration.
Without changing the cost value in Equation (3), the robustness was maximized to find the optimal combination of CIWi and ∆i. In other words, the schedule robustness was increased by assigning the FTD first to the jobs with high CIWs.
The optimization of robustness and cost is a tradeoff. In a certain range, the two variables are positively correlated with each other. Both variables will be optimized at the equilibrium point of the two objective values.
(2) Robustness-constrained time/cost tradeoff
The sub-model of the robustness-constrained time/cost tradeoff can be obtained, after transforming the robustness objective function of our model into a constraint:
s. t.$\sum _ { i = 1 } ^ { n } \left( C I W _ { i } \times \Delta _ { i } \right) \geq R ^ { * }$ (8)
where R* is the lower bound of schedule robustness.
Since the robustness function has been transformed into a constraint, the sub-model has two objective functions, respectively for time and cost. The time/cost tradeoff is to minimize the time and cost at the same time.
The time T has a positive correlation with FTD ∆i. The longer the T, the greater the FTD ∆i, the higher the resource occupancy. A high resource occupancy means a high cost. The inverse is also true. Hence, time and cost are positively correlated with each other. The sub-problem is to optimize both under the specified constraints.
(3) Cost-constrained time/robustness tradeoff
The sub-model of cost-constrained time/robustness tradeoff can be obtained, after transforming the cost objective function of our model into a constraint:
s. t. $\sum _ { i = 1 } ^ { n } \sum _ { k = 1 } ^ { K } c _ { k } \times \left( d _ { i } + \Delta _ { i } \right) \times r _ { i k } \leq C ^ { * }$ (9)
where C* is upper bound of production cost.
This sub-model attempts to minimize the time and maximize the robustness under the cost constraint. Without changing the time in Equation (1), the robustness was adjusted to find the optimal combination of CIWi and ∆i. Both time and robustness can be optimized at the equilibrium point of the two objective values.
The multi-objective tradeoff optimization in this paper is an NP-hard problem. This chapter puts forward an intelligent optimization algorithm to solve the problem. As shown in Figure 1, two optimization strategies were designed for problem solving, namely, the elite selection strategy for genetic replication and the tradeoff strategy for the three objectives. The two strategies were combined with the GA to improve the convergence speed and operation efficiency.
Figure 1. The flow chart of the proposed algorithm
4.1 Fitness calculation and solution comparison
Two of the key difficulties in GA solution of multi-objective problems are computing individual fitness and comparing feasible solutions. Here, the individual fitness is calculated by non-dominated ranking (Table 1), and two randomly selected chromosomes are compared in the following steps:
Step 1: For two individuals s1 and s2, their feasible solutions were compared in terms of time, robustness and cost. The individual with shorter time, higher robustness and lower cost was the better one and ranked in front.
Step 2: The two individuals have no dominance relationship if their relative significance could not be judged by the three factors. In this case, the two individuals were further compared by congestion degree. For each individual, the congestion degree of an objective value refers to the closeness of the value to the ranking of the individual. The congestion degrees of the three objectives were added up and normalized as the overall congestion degree of the individual. The higher the result, the more significant the individual.
Table 1. An example of non-dominated ranking
|
Objective function value |
S1 |
S2 |
S3 |
S4 |
S5 |
|
Time |
20 |
22 |
23 |
18 |
25 |
|
Robust value |
300 |
280 |
340 |
310 |
380 |
|
Cost |
6000 |
6500 |
5800 |
6200 |
5600 |
Next, individuals s1 and s3 were contrasted in terms of the three objective values. Compared with individual s3, individual s1 had a short time, but a small robustness and a high cost. It is impossible to directly determine which individual is superior, indicating that the two individuals have no dominance relationship. Then, the overall congestion degrees of them were computed by Step 2. The results show that individual s1 had a larger overall congestion degree than individual s3, and was thus ranked ahead of the latter.
4.2 Elite selection
The elite selection strategy is implemented in the following steps:
Step 1: The three objective values of each individual in the current population were calculated in turn. Then, the dominance relationship, overall congestion degree and relative significance of each individual were determined. Finally, all individuals were sorted by the non-dominated ranking method.
Step 2: The top-ranking individuals in the population were considered elites, and were directly retained in the next generation.
The retention of the selected elites ensures that the GA will gradually converge to the optimal solution, with the increase in the number of genetic iterations.
Three different plans (V1, V2 and V3) were designed to verify the effect of the proposed algorithm, which is based on elite selection and objective tradeoff. V1 is the GA coupling non-dominated ranking, V2 is the GA based on objective tradeoff, and V3 is the GA integrating objective tradeoff and elite selection. The same termination conditions were set for all three plans. The parameters of the calculation example are listed in Table 2 below.
Table 2. Parameter setting
|
Parameter |
Value |
|
The non-virtual activity number of the example N |
10,20,30,40 |
|
The number of examples generated under a non-virtual active number |
10 |
|
Number of starting and terminating activities of examples |
Random selection from 2, 3 and 4 |
|
Maximum number of successive activities |
4 |
|
The duration of the activity di |
[1,10] |
|
Resource requirements for activities rik |
[1,10] |
|
Project deadline D |
$D = p _ { D } \times C L _ { \max }$ |
|
Resource types K |
2 |
|
Availability of resources Rk |
1.0,1.2,1.4 |
|
Resource cost ck |
[1,10] |
|
Activity weight wi |
[1,10] |
Table 3. Simulation results
|
N |
V1 |
V2 |
V3 |
||||||
|
AT |
AC |
AD |
AT |
AC |
AD |
AT |
AC |
AD |
|
|
10 |
13.12 |
0.39 |
0.56 |
13.22 |
0.38 |
0.58 |
13.18 |
0.32 |
0.16 |
|
20 |
22.78 |
0.46 |
0.68 |
22.83 |
0.44 |
0.69 |
21.45 |
0.34 |
0.22 |
|
30 |
38.54 |
0.41 |
0.66 |
38.21 |
0.37 |
0.68 |
35.63 |
0.38 |
0.26 |
|
40 |
42.31 |
0.32 |
0.77 |
42.11 |
0.33 |
0.76 |
41.15 |
0.45 |
0.21 |
|
N |
1.6 |
1.8 |
2.0 |
||||||
|
ADmin |
ACmin |
ARmax |
ADmin |
ACmin |
ARmax |
ADmin |
ACmin |
ARmax |
|
|
10 |
35.21 |
4321.7 |
839.3 |
35.27 |
4312.8 |
825.4 |
35.26 |
4356.8 |
826.4 |
|
20 |
53.63 |
9341.3 |
2766.5 |
53.83 |
9325.7 |
2735.4 |
54.02 |
9421.5 |
2861.3 |
|
30 |
77.82 |
17235.3 |
6342.1 |
77.71 |
17123.2 |
6258.9 |
76.82 |
17123.5 |
6421.5 |
|
40 |
71.21 |
12362.4 |
4457.3 |
71.71 |
12562.3 |
4463.5 |
72.56 |
13214.5 |
4572.1 |
Next, V2 was simulated under three new maximum durations ($p _ { D } = 1.6$, 1.8 and 2.0). The sensitivity of V2 to the maximum duration was analyzed based on the simulation results.
As shown in Table 4, there was no significant difference for ADmin, ACmin and ARmax under the three maximum durations. This means the three optimization objectives are all insensitive to the maximum duration.
This paper optimizes the multi-objective JSP through the tradeoff of time, cost and robustness under uncertain environment. Firstly, the research problem was clarified and the related variables were defined. Then, a multi-objective tradeoff optimization model was constructed, aiming to minimize the time and cost and to maximize the time. After that, the model was decomposed into three dual-objective sub-models for in-depth discussion, revealing the tradeoff relations between the three objectives. Finally, a GA coupling non-dominated ranking was designed to solve the established model.
This work was supported by basic Scientific Research project of Department of Education of Heilongjiang Province (135109523, Multi-objective Integrated production Planning system and Optimization based on ERP).
[1] Leung, S.C.H., Tsang, S.O.S., Ng, W.L., Wu, Y. (2007). A robust optimization model for multi-site production planning problem in an uncertain environment. European Journal of Operational Research, 181(1): 224-238. https://doi.org/10.1016/j.ejor.2006.06.011
[2] Ozguven, E.E., Ozbay, K. (2013). A secure and efficient inventory management system for disasters. Transportation Research Part C: Emerging Technologies, 29: 171-196. https://doi.org/10.1016/j.trc.2011.08.012
[3] Rebecca, N.S.M., Sulaiman, M.H., Mustaffa, Z, Daniyal, H. (2017). Optimal reactive power dispatch solution by loss minimization using moth-flame optimization technique. Applied Soft Computing, 59: 210-222. https://doi.org/10.1016/j.asoc.2017.05.057
[4] Zidani, H., Pagnacco, E., Sampaio, R., Rachid, E., Cursi, E. (2013). Multi-objective optimization by a new hybridized method: applications to random mechanical systems. Engineering Optimization, 45(8): 917-939. https://doi.org/10.1080/0305215X.2012.713355
[5] Boudaher, E., Hoorfar, A. (2015). Electromagnetic optimization using mixed-parameter and multiobjective covariance matrix adaptation evolution strategy. IEEE Transactions on Antennas & Propagation, 63(4): 1712-1724. https://doi.org/10.1109/TAP.2015.2398116
[6] Johnson, S.M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics, 1(1): 61-68. https://doi.org/10.1002/nav.3800010110
[7] Helal, A.M., Abdelbar, A.M. (2014). Incorporating domain-specific heuristics in a particle swarm optimization approach to the quadratic assignment problem. Memetic Computing, 6(4): 241-254. https://doi.org/10.1007/s12293-014-0141-y
[8] Wang, X., Liang, G., Zhang, C., Shao, X. (2010). A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. International Journal of Advanced Manufacturing Technology, 51(5-8): 757-767. https://doi.org/10.1007/s00170-010-2642-2
[9] Yan, H.S., Wan, X.Q., Xiong, F.L. (2015). Integrated production planning and scheduling for a mixed batch job-shop based on alternant iterative genetic algorithm. Journal of the Operational Research Society, 66(8): 1250-1258. https://doi.org/10.1057/jors.2014.88
[10] Sun, G., Bin, S. (2017). Router-level internet topology evolution model based on multi-subnet composited complex network model. Journal of Internet Technology, 18(6): 1275-1283. https://doi.org/10.6138/JIT.2017.18.6.20140617
[11] de Reyck, B., Demeulemeester, E., Herroelen, W. (2015). Local search methods for the discrete time/resource trade-off problem in project networks. Naval Research Logistics, 45(6): 553-578. https://doi.org/10.1002/(SICI)1520-6750(199809)45:6<553::AID-NAV2>3.0.CO;2-1
[12] Wiesemann, W., Kuhn, D., Rustem, B. (2012). Multi-resource allocation in stochastic project scheduling. Annals of Operations Research, 193(1): 193-220. https://doi.org/10.1007/s10479-008-0486-z
[13] Erenguc, S.S., Ahn, T., Conway, D.G. (2015). The resource constrained project scheduling problem with multiple crashable modes: An exact solution method. Naval Research Logistics, 48(2): 107-127. https://doi.org/10.1002/1520-6750(200103)48:2<107::AID-NAV1>3.0.CO;2-9
[14] Deirmenci, G., Azizolu, M. (2013). Branch and bound based solution algorithms for the budget constrained discrete time/cost trade-off problem. Journal of the Operational Research Society, 64(10): 1474-1484. https://doi.org/10.1057/jors.2012.14
[15] Lei, L., Pinedo, M., Lian, Q. (2015). Personnel scheduling and supplies provisioning in emergency relief operations. Annals of Operations Research, 235(1): 487-515. https://doi.org/10.1007/s10479-015-1990-6
[16] Mazidi, M., Zakariazadeh, A., Jadid, S., Siano, P. (2014). Integrated scheduling of renewable generation and demand response programs in a microgrid. Energy Conversion and Management, 86: 1118-1127. https://doi.org/10.1016/j.enconman.2014.06.078
[17] Hao, X., Lin, L., Gen, M. (2014). An effective multi-objective EDA for robust resource constrained project scheduling with uncertain durations. Procedia Computer Science, 36: 571-578. https://doi.org/10.1016/j.procs.2014.09.056
[18] Qi, J.J., Liu, Y.J., Lei, H.T., Guo, B. (2014). Solving the multi-mode resource availability cost problem in project scheduling based on modified particle swarm optimization. Arabian Journal for Science & Engineering, 39(6): 5279-5288. https://doi.org/10.1007/s13369-014-1162-z
[19] Gomes, H.C., Francisco, D.A.D.N., Souza, M.J.F. (2014). Multi-objective metaheuristic algorithms for the resource-constrained project scheduling problem with precedence relations. Computers & Operations Research, 44: 92-104. https://doi.org/10.1016/j.cor.2013.11.002
[20] Chen, L., Zhang, Z. (2016). Preemption resource-constrained project scheduling problems with fuzzy random duration and resource availabilities. Journal of the Chinese Institute of Industrial Engineers, 33(6): 10-21. https://doi.org/10.1080/21681015.2016.1140089
[21] Sun, G., Bin, S. (2018). A opinion leaders detecting algorithm in multi-relationship online social networks. Multimedia Tools and Applications, 77(4): 4295-4307. https://doi.org/10.14257/ijhit.2016.9.5.33
