OPEN ACCESS
Jobshop 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 multiobjective jobshop scheduling problem (JSP) is optimized based on the tradeoff between time, cost and robustness. Firstly, a multiobjective 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 nondominated ranking was designed to solve the multiobjective 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 multiobjective JSP under various constraints.
jobshop scheduling problem (JSP), multiobjective 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 jobshops, 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 jobshop scheduling problem (JSP) [12].
Jobshop scheduling should fully rationalize job sequencing based on urgency and allocate resources to minimize waste. The resulting schedule must be executed strictly by jobshops. 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 jobshop 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 jobshop scheduling, in the case that the optimization of a single index may undermine that of the other indices.
This paper explores the multiobjective 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 twomachine scheduling, inspiring a wave of research on the JSP. Considering the complexity of jobshop 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 nondeterministic polynomialtime (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 NPhardness, 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 jobshop based on the advanced GA. Yan et al. [9] designed a GA to create the jobshop scheduling model and algorithm for complex jobshop scheduling.
Since jobshop scheduling is fundamentally multiobjective, 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 resourceconstrained time/cost tradeoff problem under multimode conditions, adopted the branchandbound 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 discretetime/cost tradeoff of largescale JSPs.
Recent years saw a rising research interests in multiobjective 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 multiobjective resource constrained scheduling problem into a singleobjective 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 jobshop can be expressed as an activityonnode 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 B_{k}, and the occupancy cost per unit time as c_{k}. For job i, the start time is denoted as S_{i}, the processing duration as d_{i}, the demand for resource k as r_{ik}, and the delay cost per unit time as w_{i}.
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 jobshop 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 Succ_{i } 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 (CIW_{i}) 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 CIW_{i}, 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=S_{n+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 multiobjective 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 V^{t} 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 S_{n+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 s_{i} 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 multiobjective optimization model was divided into three parts for indepth discussion. The three parts are the timeconstrained tradeoff between robustness and cost, the robustnessconstrained tradeoff between time and cost, and the costconstrained tradeoff between time and robustness.
(1) Timeconstrained robustness/cost tradeoff
The submodel of the timeconstrained 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 submodel 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 s_{i}. 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 CIW_{i} 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) Robustnessconstrained time/cost tradeoff
The submodel of the robustnessconstrained 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 submodel 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 subproblem is to optimize both under the specified constraints.
(3) Costconstrained time/robustness tradeoff
The submodel of costconstrained 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 submodel 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 CIW_{i} and ∆_{i}. Both time and robustness can be optimized at the equilibrium point of the two objective values.
The multiobjective tradeoff optimization in this paper is an NPhard 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 multiobjective problems are computing individual fitness and comparing feasible solutions. Here, the individual fitness is calculated by nondominated ranking (Table 1), and two randomly selected chromosomes are compared in the following steps:
Step 1: For two individuals s_{1} and s_{2}, 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 nondominated 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 s_{1} and s_{3} were contrasted in terms of the three objective values. Compared with individual s_{3}, individual s_{1} 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 s_{1} had a larger overall congestion degree than individual s_{3}, 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 nondominated ranking method.
Step 2: The topranking 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 nondominated 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 nonvirtual activity number of the example N 
10,20,30,40 
The number of examples generated under a nonvirtual 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 d_{i} 
[1,10] 
Resource requirements for activities r_{ik} 
[1,10] 
Project deadline D 
$D = p _ { D } \times C L _ { \max }$ 
Resource types K 
2 
Availability of resources R_{k} 
1.0,1.2,1.4 
Resource cost c_{k} 
[1,10] 
Activity weight w_{i} 
[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 

AD_{min} 
AC_{min} 
AR_{max} 
AD_{min} 
AC_{min} 
AR_{max} 
AD_{min} 
AC_{min} 
AR_{max} 

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 AD_{min}, AC_{min} and AR_{max} under the three maximum durations. This means the three optimization objectives are all insensitive to the maximum duration.
This paper optimizes the multiobjective 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 multiobjective 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 dualobjective submodels for indepth discussion, revealing the tradeoff relations between the three objectives. Finally, a GA coupling nondominated 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, Multiobjective 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 multisite production planning problem in an uncertain environment. European Journal of Operational Research, 181(1): 224238. 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: 171196. 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 mothflame optimization technique. Applied Soft Computing, 59: 210222. https://doi.org/10.1016/j.asoc.2017.05.057
[4] Zidani, H., Pagnacco, E., Sampaio, R., Rachid, E., Cursi, E. (2013). Multiobjective optimization by a new hybridized method: applications to random mechanical systems. Engineering Optimization, 45(8): 917939. https://doi.org/10.1080/0305215X.2012.713355
[5] Boudaher, E., Hoorfar, A. (2015). Electromagnetic optimization using mixedparameter and multiobjective covariance matrix adaptation evolution strategy. IEEE Transactions on Antennas & Propagation, 63(4): 17121724. https://doi.org/10.1109/TAP.2015.2398116
[6] Johnson, S.M. (1954). Optimal two and threestage production schedules with setup times included. Naval Research Logistics, 1(1): 6168. https://doi.org/10.1002/nav.3800010110
[7] Helal, A.M., Abdelbar, A.M. (2014). Incorporating domainspecific heuristics in a particle swarm optimization approach to the quadratic assignment problem. Memetic Computing, 6(4): 241254. https://doi.org/10.1007/s122930140141y
[8] Wang, X., Liang, G., Zhang, C., Shao, X. (2010). A multiobjective genetic algorithm based on immune and entropy principle for flexible jobshop scheduling problem. International Journal of Advanced Manufacturing Technology, 51(58): 757767. https://doi.org/10.1007/s0017001026422
[9] Yan, H.S., Wan, X.Q., Xiong, F.L. (2015). Integrated production planning and scheduling for a mixed batch jobshop based on alternant iterative genetic algorithm. Journal of the Operational Research Society, 66(8): 12501258. https://doi.org/10.1057/jors.2014.88
[10] Sun, G., Bin, S. (2017). Routerlevel internet topology evolution model based on multisubnet composited complex network model. Journal of Internet Technology, 18(6): 12751283. 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 tradeoff problem in project networks. Naval Research Logistics, 45(6): 553578. https://doi.org/10.1002/(SICI)15206750(199809)45:6<553::AIDNAV2>3.0.CO;21
[12] Wiesemann, W., Kuhn, D., Rustem, B. (2012). Multiresource allocation in stochastic project scheduling. Annals of Operations Research, 193(1): 193220. https://doi.org/10.1007/s104790080486z
[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): 107127. https://doi.org/10.1002/15206750(200103)48:2<107::AIDNAV1>3.0.CO;29
[14] Deirmenci, G., Azizolu, M. (2013). Branch and bound based solution algorithms for the budget constrained discrete time/cost tradeoff problem. Journal of the Operational Research Society, 64(10): 14741484. 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): 487515. https://doi.org/10.1007/s1047901519906
[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: 11181127. https://doi.org/10.1016/j.enconman.2014.06.078
[17] Hao, X., Lin, L., Gen, M. (2014). An effective multiobjective EDA for robust resource constrained project scheduling with uncertain durations. Procedia Computer Science, 36: 571578. 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 multimode resource availability cost problem in project scheduling based on modified particle swarm optimization. Arabian Journal for Science & Engineering, 39(6): 52795288. https://doi.org/10.1007/s133690141162z
[19] Gomes, H.C., Francisco, D.A.D.N., Souza, M.J.F. (2014). Multiobjective metaheuristic algorithms for the resourceconstrained project scheduling problem with precedence relations. Computers & Operations Research, 44: 92104. https://doi.org/10.1016/j.cor.2013.11.002
[20] Chen, L., Zhang, Z. (2016). Preemption resourceconstrained project scheduling problems with fuzzy random duration and resource availabilities. Journal of the Chinese Institute of Industrial Engineers, 33(6): 1021. https://doi.org/10.1080/21681015.2016.1140089
[21] Sun, G., Bin, S. (2018). A opinion leaders detecting algorithm in multirelationship online social networks. Multimedia Tools and Applications, 77(4): 42954307. https://doi.org/10.14257/ijhit.2016.9.5.33