Research On Dynamic Scheduling Problems Based On Dynamic Optimization

Production scheduling is the allocation of available production resources meeting certain production constraints to completing a set of jobs in order to optimize one or more objectives. Previous work mostly focused on static scheduling in which all the information is available at the beginning of the planning horizon and is assumed unchanged during the period. However, there are always various unpredictable real-time events happening in the real-world production environments, such as dynamic job arrivals, machine breakdowns, job processing time changes, and so on. These disturbance events will upset the plan and cause the initially feasible schedule to become poor and sometimes infeasible. It is necessary to adjust the schedule or make a new schedule quickly to adapt the changed production environment and conditions. Such problems can be summed up in dynamic scheduling problems. The research on dynamic scheduling has more realistic significance than static scheduling and it is the major difficulty to be solved urgently in industry. The general static scheduling algorithms mainly solve the deterministic scheduling problem and cannot adapt the change of environments, therefore are not suitable for the dynamic scheduling problems. Since the dynamic optimization algorithm can adapt the change of environments and track the movement of the optimal solution, it has become a hot topic in research theory in the world.Based on the analysis of the dynamic factors, taking the single machine scheduling as background, this paper studies the basic research on dynamic optimization and proposes a dynamic differential evolution algorithm. On the other hand, taking the SCC production scheduling as background, this paper studies the application research on dynamic optimization and develops an incremental mechanism based dynamic differential evolution algorithm for dynamic scheduling problem of SCC production. By embedding this algorithm, the decision support systems (DSS) software for the SCC production scheduling is developed. The content of the dissertation is summarized as follows.1) The dynamic factors in the dynamic schedule have been analyzed. Taking the general production environment and the steel production environment as backgrounds, this paper analyzes the common dynamic factors in the dynamic scheduling and the special dynamic factors in the steel production, respectively. Real-time events are summarized and classified. According to the characteristics of real-time events, the causes and source of real-time events are analyzed. For different real-time events, different rescheduling methods are proposed.2) The common due date total earliness/tardiness dynamic single machine scheduling problem with dynamic release time has been investigated. The problem is to schedule a set of jobs with dynamic release time and a common due date on a single machine. The goal is to find a schedule to minimize the total weighted earliness and tardiness penalties. Based on the characteristics of the problem, a mathematical programming model is formulated. To solve the problem, the permutation-based hybrid differential evolution and estimation of distribution algorithm (DE&EDA) method is proposed. The algorithm combines differential information obtained by DE with global information extracted by EDA to create promising solutions.In order to strengthen the performance of the algorithm, a local search algorithm is applied. The computational results on benchmark data demonstrate that the proposed algorithm is effective.3) The dynamic single machine scheduling problem with sequence dependent setup times has been studied. In such a problem, jobs arrive over time and only can be scheduled after their arrivals because the information of jobs is unknown in advance. The objective is to minimize the maximum lateness. Based on the characteristics of the problem, a mathematical programming model for a given time window is formulated. Considering the complexity of the problem, a dynamic differential evolution algorithm that adapts the schedule when new jobs arrive is proposed. In the proposed DE algorithm for the scheduling problem, the individual is based on the discrete job permutation. A speed-up method is developed to improve the efficiency of the algorithm. The computational results demonstrate that the proposed algorithm is fast and effective.4) The dynamic scheduling problem of SCC production has been investigated. The goal of the problem is to reschedule production in response to unexpected real-time events while adapting the changed production environment and conditions. Considering the constraints of practical technological requirements and the real-time information, and taking the processing time of the charge as the decision variable, a mathematical programming model under real-time events is formulated. The objective is to minimize the total penalties including four terms that are the cast break penalty, the total charge waiting time penalty, the processing time deviation penalty, and the makespan penalty.5) To deal with the dynamic scheduling problem of SCC production mentioned above, an incremental mechanism based dynamic differential evolution algortithm is proposed. This involves (1) Adapting the good solutions in the previous environment to the current environment under the incremental mechanism, and then the new problem is solved by DE; (2) improvement of the DE algorithm by introducing a memory scheme and an external archive scheme as well as incorporating these schemes in a modified mutation strategy; (3) introduction of a real-coded matrix for the individual representation. In the proposed mutation strategy, a memory scheme is to store and use information of the population from the previous generation and an external archive scheme is to store recently explored superior solutions. Numerical results on both randomly generated instances and practical production data considering the real-time information demonstrate that the proposed algorithm is effective.6) Taking the SCC production in the steel industry as background, a SCC scheduling decision support system for the practical production is developed based on the optimization model and algorithm described above. It could not only solve the static scheduling problem, but also handle the dynamic scheduling problem in response to the real-time events. The computational experiments are carried out and the results verify the efficiency of the proposed algorithm and the stability of the system.