Abstract
Abstract
Product collaborative design scheduling problem (PCDSP) has received increasing attention in the engineering field for its popularity in manufacturing and supply chain systems. Although many scholars have achieved many useful results in Job-shop scheduling problem (JSP), the research work of PCDSP is still lacking. Moreover, the fuzziness, dynamics and multi-objective of PCD pose a great challenge for enterprises making quick response to unplanned perturbations. Thus, in this paper, multi-objective dynamic fuzzy scheduling and its solution algorithm are presented. Emergencies cases are analyzed and dynamic scheduling procedure based on event-driven and lifecycle-driven is developed firstly. The fuzziness of PCD process is studied meanwhile fuzzy triangular number and fuzzy trapezoid number are used to express the fuzziness. Based on this, a multi-objective dynamic fuzzy scheduling model aiming to minimum the makespan and tardiness penalty is constructed. As a solution, multi-objective dynamic adaptive scheduling algorithm, based on bi-layer coding strategy and self-adaptive double point crossover and self-adaptive mutation, is proposed following closely. Finally, analytic results from a case of a wind turbine are used to illustrate the model and method proposed in this paper. With the analysis, it can provide insight into ways of improving the strategic and operational decision making for enterprises.
Keywords
Introduction
Prosperity of market and rapid development of technology lead to an increasing complexity of products, which causes that enterprise have to deal with ever-bigger information. Consequently, it becomes more and more intractable for an enterprise to complete all transactions of product development independently within the prescribed time limit [1]. Camrinha et al. suggested an effective way of integrating customers, suppliers, scientific research institutes and other units together to accomplish a product, which is defined as Product Collaborative Design (PCD) [2, 3].
As a distributed cooperative system, one of the gordian knots is guaranteeing all tasks succeed in while ensuring design cost and customer satisfaction over the duration of development under uncertain environment. Actually, due to the multifarious indeterminate factors of PCD, the processing time and due date of design task are difficult to determined accurately [4]. Meanwhile, inevitable perturbations such as rush orders, customer requirements changes, customer churn and employee turnover are always hindering production progress and even lead to mission abort if handled improperly [5]. In this situation, it is fundamentally crucial to devise a PCD scheduling (PCDS) strategy for reducing the impact and keep high efficiency.
In this paper, a multi-objective dynamic fuzzy scheduling (MDFS) model and its algorithm considering the emergencies in PCD are presented to solve above dilemma. Based on the general information of PCD, dynamic scheduling procedure is proposed to manage the possible perturbations, and fuzzy trapezoid numbers are used to express the fuzziness of task process time and due date. Hereafter, regard makespan and tardiness penalty caused by emergency as the objectives of multipurpose optimal model, a multi-objective heuristic genetic algorithm, multi-objective dynamic adaptive scheduling algorithm (MODASA) is developed as the model solution.
Related works
Attempts to solve this dilemma have resulted in the development of some effective ways, which mainly focuses on two aspects, namely the scheduling model and algorithm.
For scheduling model, Upendra Belhe and Andrew Kusiak used directed graphs to represent multiple design projects competing for the limited available resources and the scheduling problem is decomposed into a series of multidimensional (multisource) knapsack problems [6]. Peter et al. developed a scheduling model based on LR and SDP to resolve the design projects with uncertain number of iterations [7]. Christian et al. proposed a flow network model taking advantage on the flow structure to resource-constrained project static and dynamic scheduling problem [8]. Danilovic and Brown formalized an approach using a domain mapping matrix (DMM) to compare two DSMs of different project domains, then activities schedule is conducted based the priority of the projects [9]. Pan et al. developed a model based on synchronous mapping from weighted directed graph to DSM and polychromatic sets to transform related information needed for design task scheduling [10]. Browning and Yassine addressed the static resource-constrained multi-project scheduling problem (RCMPSP) with two lateness objectives, project lateness and portfolio lateness [11]. Li et al. proposed a Multi-mode Optimal Scheduling of Product Design Project Based on Person- task- resource Matching Degree [12]. Tanguy Lapègue et al. presented a CP model which deals simultaneously with the assignment of tasks and the design of personnel schedules in order to solve a real-world problem [13].
For algorithm, there are many kinds of improved solutions. Lam et al. developed a scheduling Genetic Algorithm (GA) to minimize product design time [14]. Pedro Gomez Gasquet et al. developed a modified GA for collaborative scheduling of products-packages service [15]. Krishnamoorthy proposed a Lagrangean approach for solving the Personnel Task Scheduling Problem (PTSP) [16]. Besides, competent genetic algorithms [17], ant colony algorithms [18] simulated annealing (SA) [18] and Particle swarm optimization (PSO) [19] and many other algorithm or integrated [20] were used in PCD scheduling.
In summary, most existing approaches have made some achievements. However, extra-absolute of these researches, such as fuzziness considered inadequately, inaccuracy of multipurpose optimization and neglect of accidents also create some problems in the practical application.
Problem formulation
Basic Scheduling model
Suppose that a PCD organization contains m designers and a product is decomposed into n tasks after careful analysis. Then, the basic objective is that all tasks are assigned to designers excellently based on the sequence of activities. Simultaneously, time parameters of each task are clear and definite. Moreover, the makespan is the minimum in that state, as shown in Equation (1).
To accomplish this, we begin by defining the following basic definitions and descriptions.
According to above definitions, descriptions and Equations (1–7), a basic scheduling formulation can be established on the context of ideal condition where all time parameters are explicit and there are no any interference factors.
Emergency cases
PCD involves multidisciplinary synergy, cross-organizations and distributed designers. Due to rush orders, customer requirements changes, and customer churn etc., collaborative work environment is always in a state of dynamic change, which leads to a greatly increasing complexity and uncertainty of task procedures. This scenario argues that scheduling procedure should take impossible emergencies into consideration. An immediate consequence of emergency is task tardiness. Thus, tardiness penalty f2 is considered to minimize effect of emergency. For PCD, tardiness occurs once CT i > DD i . Let λ i indicate the penalty coefficient of T i , the unit tardiness of tardy Ta i .
Event-driven, lifecycle-driven and hybrid-driven are three most frequent dynamic scheduling methods to cope with emergency [21]. Event-driven means that rescheduling is activated only when task set changes because of accidents. Lifecycle-driven implies that rescheduling is implemented every once in a while no matter what happens at set intervals. Obviously, lifecycle-driven scheduling is able to maintain task set at a certain stability but incapable of tackling emergencies while event-driven is just the reverse. Thus, hybrid-driven scheduling, synthesizing advantages both of event-driven and lifecycle-driven, can not only deal with unexpected incidents but also keep the relative stability of the collaborative system. Therefore, this paper stresses on the dynamic scheduling based on hybrid-driven, as shown in Fig. 1.
On the premise of minimizing the makespan ofPCD, dynamic scheduling should reduce the tardiness penalty where possible. Basic on Equations (1) and (8), the optimization objective function containing completion time and tardiness penalty can be formed as Equation (9).
Here, T k denotes the time that M k accomplish the last tasks. bt h indicates the start time of the h th rescheduling. Tai,h,S3 implies the set of tasks being resolved while the h th rescheduling starts. Tai,S1,k means the set of tasks in state S1 by M k . RT k represents the remaining time of M k to fulfill the tasks in S3. ΔT h signifies the h th rescheduling period. t e expresses the time that rescheduling occurs.
Actually, human-cantered factors are incorporated into PCDS, thus, considering processing time due to man-made factors and fuzzy due date, which tolerates a certain amount of delay in the due date, may be more appropriate [22]. Then fuzzy triangular number [23] is introduced to describe the fuzziness processing time and fuzzy trapezoid number [24] is used to represent the fuzzy due date.
Fuzzy processing time
In the process of collaborative design, man-made factors cannot be eliminated. Using fuzzy variable to descript processing time is more realistic. Introduce a fuzzy triangular number , , and denotes the pessimistic, the most possible and optimistic processing time respectively. As shown in Fig. 2a, membership function μ
ijk
(x) is as following Equation (12).
Analogously, fuzzy completion time can be indicated by a fuzzy triangular number . , and denotes the pessimistic, the most possible and optimisticcompletion time respectively. As shown in Fig. 2b, membership function μ ijk (c) is as following Equation (13).
The due date of product design schemes is a key influence factor of customer satisfaction and manufacture order. The fuzziness of design process results in an uncertain completion time. Meanwhile, due date varies by different customers. Thus, fuzzy due date can be represented by a fuzzy trapezoid number. As shown in Fig. 2c, is expected rather others. The membership function μ ijk (d) can be formulated as Equation (14).
Based on the aforementioned, PCDS is actually a multi-objective dynamic fuzzy scheduling problem. The objective functions can be described as Equations (15) and (16). Constraints are shown in Equations (17–23).
Algorithm
The PCDS problem under study is NP hard even on the context of the deterministic processing time case. Accordingly, traditional optimization methods are hardly to achieve an optimal solution [25]. Many heuristic solutions, such as Genetic Algorithm (GA), Simulated Annealing (SA), Particle Swarm Optimization (PSO) and others, have been developed for optimization. Among these novel methods, GA has been well documented in the literature and obtains a predictive effect for a variety of optimization problems. Thus, in this paper, a model solution based on GA, multi-objective dynamic adaptive scheduling algorithm (MODASA) is proposed for the problem under study.
The MODASA achieves a dynamic flexible allocation of task-designer based on the bi-layer coding strategy formed by the fusion of task sequences and designers attributes. This method is able to call the designers and resources competent for tasks with the minimum tardiness penalties when the accident and even task suspension appears. Consequently, the influence of time delay can be reduced and the efficiency of PCD can be improved. Figure 3 shows the algorithm process of the MODASA.
Initialization parameter
All related parameter should be initialized firstly. Let t indicate the evolutional generation, BT k denote the start time of D k performing a task and W means the maximum number of the tasks. h = 0 and bt h = 0.
Encoding chromosome
According to the characteristic of this problem, a bi-layer coding strategy formed by the fusion of tasks sequences and designers attributes is proposed. The first layer is encoded based on design tasks sequences. All procedures of a task are specified a unified symbol and explained according to their appearance order in chromosome. Suppose a chromosome is [231122313], where 1, 2, 3, 4 and 5 represent Ta1, Ta2, Ta3, Ta4 and Ta5 respectively. Due to each task includes 3 design sequences, thus each number appears five times in a chromosome. The second layer is designer code of the process, which means P ij can be formed by any one of D ij . As shown in Fig. 4, it is a 3 × 3 example. P21 of Ta2 can be completed by one of D21. By such analogy, the bi-layer coding strategy is straightforward able to achieve the replacement of resources when emergencies happen.
D ij is selected to carry out P ij according to the principle that the processing time is minimum and no conflict appears. If j = 1, PT ijk can be calculated by Equation (7), otherwise, Equation (6) will be used.
Fitness
The objective value is calculated according to Equations (15) and (16). Then define a joint objective function F i = f1 + λ i f2 as the fitness of individual i.
Selection
This paper uses the roulette wheel method to select the parent chromosomes i with probability prob
i
from the population with popsize individuals.
This study adopts self-adaptive double point crossover to increase the population diversity and to prevent the operation of algorithm premature and stagnation. As shown in Fig. 5.
The self-adaptive function of crossover rate prob C is defined as Equation (25)
The mutation mechanism randomly selects a gene according to the mutation rate and alters its value. Meanwhile, adaptive mutation probability is used to improve the convergence speed, and the adaptive adjustment function is formulated as Equation (26).
As shown in Fig. 6, Ta6 is randomly selected and altered to Ta9.
If the maximal generation is reached, namely t = T, then stop and output F i and scheduling scheme; otherwise, go to Section 4.1.4 to perform the next iteration.
Dynamic scheduling
Based on the steps in Section 4.1, a common schedule can be completed. However, once an emergency occurs, additional measures may be adopted. In some cases, such as requirement changes, rush order and natural disaster, rescheduling must be launched immediately. At that moment, all related tasks and its processes are classified into S2. Meanwhile, these tasks enjoy privileges of taking precedence over other tasks when the emergency settled. However, in another cases, such as operational error and technical improvement, completion status of tasks should be checked before rescheduling launched. If the task has been completed, rescheduling is needless. Otherwise, rescheduling must be activated promptly. The pseudo code of the dynamic scheduling algorithm is as following.
Pseudo code
The pseudo code of the MODASA for multi-objective fuzzy scheduling is as following.
Case study
To evaluate the performance of the proposed model and algorithm, a case study is conducted in this section. As a complex product, a wind turbine usually consists of thousands of parts. Thus PCD is an applicable work patterns. Generally, a wind turbine contains 10 key components, which are equivalent to 10 design tasks. Suppose that each task includes 3 processes. All tasks are carried out by 3 designers from different institutions. Essential Information about tasks and designers are illustrated in Table 1, where [175,180] means that the optimum duration of due date is from 175 to 180. Without loss of generality, ST ij = ET ij = 1, the penalty coefficient λ i = 0.8, the rescheduling period ΔT k = 8, the population size popsize = 500, the maximum generation T = 500, the self-adaptive crossover probability probc1 = 0.8, probc2 = 0.6, the mutation rate probm1 = 0.1, probm2 = 0.001.
During the PCD process, two emergencies occur. M1 interrupts the task is being performed at t = 70 because of the resource conflicts and restores the work at t = 90. Due to the customer requirements changes at t = 120, the due date of Ta10 is advanced to [175,185] from [245,255].
Computational result
According to the solutions above, the value of the objective can be calculated, as shown in Fig. 7, which is the Gantt chart of PCD tasks in the context of without emergencies and considering emergencies. With the analysis, the maximum completion time of the wind turbine is 212h, while it extends to 217h when the two accidents emerge. Moreover, if we don’t conduct the dynamic scheduling, the result is shown in Fig. 7, P72 is suspended at t = 70 and P22 is tardive. In this circumstance, the PCD cycle is much greater than 317h. Consequently, the dynamic scheduling plays a positive role in improving work efficiency.
A comparison of the MODASA with the AACA [26] the SAGA [27], the MOGA [28] is conducted under the circumstances that ΔT = 50, probc1 = 0.8 and probm1 = 0.1. After running 50 times independently, the optimal results are shown in Fig. 8. And the beststatistical results are shown in Table 2. It can be seen that MODASA converges to the optimal result after 48 generations, MOGA converges to it after 76 generations, and SAGA converges to it after 149 generations while SGA converges to it after 256 generations. When running on the computer with CPU core duo E4600, basic frequency 2.4 GHZ, 2G memory, the running time by MODASA is 16.47s, the time by MOGA is 21.04s, he time by SAGA is 24.15s and it is 29.98s by AACA. Thus, the MODASA has higher stability and shorter running time than others.
Further discuss
Furthermore, this paper analyses the impact of accidents on the performance of PCD. Through the changes to the rescheduling period, due dates, the variation of dynamic scheduling performance can be grasped. Analysis results are shown in Table 3.
As shown in Table 3, in column task interrupt, (1:70–90) means M1 is forced to suspend the task at t = 70 and recover at t = 90. In column due date, (10:250–180) indicates the due date of Ta10 is advanced to 180 from 250 (mid-value of the interval for convenience). and denotes the average processing cycle and the average tardiness penalty when the program runs 20 times. represents the average convergence time of running 20 times. With the analysis, it is true of an ever increasing value of the average process cycle, the deviation, the average tardiness penalty and the average convergence time over the change process from (10:250-180), (9:195-160) to (3:70–90). This kind of change explains that the due date variation for tasks with a less time have a greater impact on PCD performance. Meanwhile, on the basic of the same ΔT and due date variation, considering the task interrupt over (1:70–90), (2:70–90) to (3:70–90), there is a similar variation tendency of ever increasing for the average process cycle, the deviation, the average tardiness penalty and the average convergence time. This indicates that the designers with a well-distributed processing time have a much greater effect on PCD. Actually, these kinds of designers are usually regarded as much-needed and versatile person for an enterprise. In addition, in the process of ΔT changing from 50 to 100, the average convergence time gradually drops while the average process cycle, the deviation and the average tardiness penalty appear unstable mutations. This suggests that there is true of an optimal rescheduling period for each designer.
Conclusions
In summary, PCD scheduling problem has received increasing attention in the engineering field for its popularity in manufacturing and supply chain systems. The fuzziness, dynamics and multi-objective of PCD pose a great challenge for enterprises making quick response to unplanned perturbations. Thus, in this paper, a multi-objective fuzzy scheduling model and its algorithm was proposed. The analytical results indicated that the PCD cycle is shortened and the tardiness penalty is smaller by the method when accidents emerged. The main achievements of this paper are as following: The fuzziness of PCD was analyzed based on the practical situation. Fuzzy triangular number was introduced to represent the processing time and the completion time while fuzzy trapezoid number was used to indicate the due date. It was suggested by the results that the number of tardiness became less. Hybrid-driven scheduling, synthesizing advantages both of event-driven and lifecycle-driven, could not only deal with unexpected incidents but also kept the relative stability of the collaborative system. MODASA, based on bi-layer coding strategy, self-adaptive double point crossover and self-adaptive mutation, shown full advantages in computing speed and precision. On the premise of the same ΔT and task interrupt, the due date variation for tasks with a less time have a greater impact on PCD performance. While, the designers with a well-distributed processing time have a much greater effect on PCD in the context of the same ΔT and the due date. Moreover, there is true of an optimal rescheduling period for each designer because the average convergence time gradually drops when ΔT changes.
However, it is commonly believed that PCD scheduling is a complex problem. There are many factors influencing the efficiency of task scheduling, but in this article, only three kinds of fuzziness and two objectives are studied, which are comparatively lack when applied in real situation. Thus, it is needed to be further expounded and studied for its factors and objectives. Moreover, there are many other algorithms to resolve the problem, so new attempts to resolution of PCD scheduling will be focused in the further study.
Footnotes
Acknowledgments
This research is sponsored by National Natural Science Foundation of China under Project number 71071173, 71301176. The authors also thank to Fundamental Research Funds for the Central Universities (Project No. CDJZR12110004) and Specialized Research Fund for the Doctoral Program of Higher Education (Project 20130191120001) for partial support of this work. We are grateful for the constructive suggestions provided by the reviewers, which would improve the paper.
