The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this wor...The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this work, a novel mathematic model for the hybrid flow shop scheduling problem with unrelated parallel machine(HFSPUPM) was proposed. Additionally, an effective hybrid estimation of distribution algorithm was proposed to solve the HFSPUPM, taking advantage of the features in the mathematic model. In the optimization algorithm, a new individual representation method was adopted. The(EDA) structure was used for global search while the teaching learning based optimization(TLBO) strategy was used for local search. Based on the structure of the HFSPUPM, this work presents a series of discrete operations. Simulation results show the effectiveness of the proposed hybrid algorithm compared with other algorithms.展开更多
In this paper, we propose a multi-criteria machine-schedules decision making method that can be applied to a produc-tion environment involving several unrelated parallel machines and we will focus on three objectives:...In this paper, we propose a multi-criteria machine-schedules decision making method that can be applied to a produc-tion environment involving several unrelated parallel machines and we will focus on three objectives: minimizing makespan, total flow time, and total number of tardy jobs. The decision making method consists of three phases. In the first phase, a mathematical model of a single machine scheduling problem, of which the objective is a weighted sum of the three objectives, is constructed. Such a model will be repeatedly solved by the CPLEX in the proposed Multi-Objective Simulated Annealing (MOSA) algorithm. In the second phase, the MOSA that integrates job clustering method, job group scheduling method, and job group – machine assignment method, is employed to obtain a set of non-dominated group schedules. During this phase, CPLEX software and the bipartite weighted matching algorithm are used repeatedly as parts of the MOSA algorithm. In the last phase, the technique of data envelopment analysis is applied to determine the most preferable schedule. A practical example is then presented in order to demonstrate the applicability of the proposed decision making method.展开更多
In this paper, we consider scheduling problems with general truncated job-dependent learning effect on unrelated parallel-machine. The objective functions are to minimize total machine load, total completion (waiting)...In this paper, we consider scheduling problems with general truncated job-dependent learning effect on unrelated parallel-machine. The objective functions are to minimize total machine load, total completion (waiting) time, total absolute differences in completion (waiting) times respectively. If the number of machines is fixed, these problems can be solved in time respectively, where m is the number of machines and n is the number of jobs.展开更多
Scheduling problem is a well-known combinatorial optimization problem.An effective improved estimation of distribution algorithm(IEDA) was proposed for minimizing the makespan of the unrelated parallel machine schedul...Scheduling problem is a well-known combinatorial optimization problem.An effective improved estimation of distribution algorithm(IEDA) was proposed for minimizing the makespan of the unrelated parallel machine scheduling problem(UPMSP).Mathematical description was given for the UPMSP.The IEDA which was combined with variable neighborhood search(IEDA_VNS) was proposed to solve the UPMSP in order to improve local search ability.A new encoding method was designed for representing the feasible solutions of the UPMSP.More knowledge of the UPMSP were taken consideration in IEDA_ VNS for probability matrix which was based the processing time matrix.The simulation results show that the proposed IEDA_VNS can solve the problem effectively.展开更多
A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely no...A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.展开更多
The scheduling efficiency of the tracking and data relay satellite system（TDRSS）is strictly limited by the scheduling degrees of freedom（DoF）,including time DoF defined by jobs＇ flexible time windows and spatial ...The scheduling efficiency of the tracking and data relay satellite system（TDRSS）is strictly limited by the scheduling degrees of freedom（DoF）,including time DoF defined by jobs＇ flexible time windows and spatial DoF brought by multiple servable tracking and data relay satellites（TDRSs）.In this paper,ageneralized multiple time windows（GMTW）model is proposed to fully exploit the time and spatial DoF.Then,the improvements of service capability and job-completion probability based on the GMTW are theoretically proved.Further,an asymmetric path-relinking（APR）based heuristic job scheduling framework is presented to maximize the usage of DoF provided by the GMTW.Simulation results show that by using our proposal 11%improvement of average jobcompletion probability can be obtained.Meanwhile,the computing time of the time-to-target can be shorten to 1/9 of the GRASP.展开更多
Due to the limited transmission resources for data relay in the tracking and data relay satellite system （TDRSS）, there are many job requirements in busy days which will be discarded in the conventional job scheduli...Due to the limited transmission resources for data relay in the tracking and data relay satellite system （TDRSS）, there are many job requirements in busy days which will be discarded in the conventional job scheduling model. Therefore, the improvement of scheduling efficiency in the TDRSS can not only help to increase the resource utilities, but also to reduce the scheduling failure ratio. A model of nonhomogeneous parallel machines scheduling problems with time window （NPM-TW） is firstly built up for the TDRSS, considering the distinct features of the variable preparation time and the nonhomogeneous transmission rates for different types of antennas on each tracking and data relay satellite （TDRS）. Then, an adaptive subsequence adjustment （ASA） framework with evolutionary asymmetric path-relinking （EvAPR） is proposed to solve this problem, in which an asymmetric progressive crossover operation is involved to overcome the local optima by the conventional job inserting methods. The numerical results show that, compared with the classical greedy randomized adaptive search procedure （GRASP） algorithm, the scheduling failure ratio of jobs can be reduced over 11% on average by the proposed ASA with EvAPR.展开更多
基金Projects(61573144,61773165,61673175,61174040)supported by the National Natural Science Foundation of ChinaProject(222201717006)supported by the Fundamental Research Funds for the Central Universities,China
文摘The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this work, a novel mathematic model for the hybrid flow shop scheduling problem with unrelated parallel machine(HFSPUPM) was proposed. Additionally, an effective hybrid estimation of distribution algorithm was proposed to solve the HFSPUPM, taking advantage of the features in the mathematic model. In the optimization algorithm, a new individual representation method was adopted. The(EDA) structure was used for global search while the teaching learning based optimization(TLBO) strategy was used for local search. Based on the structure of the HFSPUPM, this work presents a series of discrete operations. Simulation results show the effectiveness of the proposed hybrid algorithm compared with other algorithms.
文摘In this paper, we propose a multi-criteria machine-schedules decision making method that can be applied to a produc-tion environment involving several unrelated parallel machines and we will focus on three objectives: minimizing makespan, total flow time, and total number of tardy jobs. The decision making method consists of three phases. In the first phase, a mathematical model of a single machine scheduling problem, of which the objective is a weighted sum of the three objectives, is constructed. Such a model will be repeatedly solved by the CPLEX in the proposed Multi-Objective Simulated Annealing (MOSA) algorithm. In the second phase, the MOSA that integrates job clustering method, job group scheduling method, and job group – machine assignment method, is employed to obtain a set of non-dominated group schedules. During this phase, CPLEX software and the bipartite weighted matching algorithm are used repeatedly as parts of the MOSA algorithm. In the last phase, the technique of data envelopment analysis is applied to determine the most preferable schedule. A practical example is then presented in order to demonstrate the applicability of the proposed decision making method.
文摘In this paper, we consider scheduling problems with general truncated job-dependent learning effect on unrelated parallel-machine. The objective functions are to minimize total machine load, total completion (waiting) time, total absolute differences in completion (waiting) times respectively. If the number of machines is fixed, these problems can be solved in time respectively, where m is the number of machines and n is the number of jobs.
基金National Natural Science Foundations of China(Nos.61573144,61174040)
文摘Scheduling problem is a well-known combinatorial optimization problem.An effective improved estimation of distribution algorithm(IEDA) was proposed for minimizing the makespan of the unrelated parallel machine scheduling problem(UPMSP).Mathematical description was given for the UPMSP.The IEDA which was combined with variable neighborhood search(IEDA_VNS) was proposed to solve the UPMSP in order to improve local search ability.A new encoding method was designed for representing the feasible solutions of the UPMSP.More knowledge of the UPMSP were taken consideration in IEDA_ VNS for probability matrix which was based the processing time matrix.The simulation results show that the proposed IEDA_VNS can solve the problem effectively.
基金supported by the National Natural Science Foundation of China (7060103570801062)
文摘A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.
基金Supported by the National Natural Science Foundation of China(91338101,91338108,61132002,6132106)Research Fund of Tsinghua University(2011Z05117)Co-innovation Laboratory of Aerospace Broadband Network Technology
文摘The scheduling efficiency of the tracking and data relay satellite system（TDRSS）is strictly limited by the scheduling degrees of freedom（DoF）,including time DoF defined by jobs＇ flexible time windows and spatial DoF brought by multiple servable tracking and data relay satellites（TDRSs）.In this paper,ageneralized multiple time windows（GMTW）model is proposed to fully exploit the time and spatial DoF.Then,the improvements of service capability and job-completion probability based on the GMTW are theoretically proved.Further,an asymmetric path-relinking（APR）based heuristic job scheduling framework is presented to maximize the usage of DoF provided by the GMTW.Simulation results show that by using our proposal 11%improvement of average jobcompletion probability can be obtained.Meanwhile,the computing time of the time-to-target can be shorten to 1/9 of the GRASP.
基金supported by the National Natural Science Foundation of China(6113200291338101+3 种基金91338108)the National S&T Major Project(2011ZX03004-001-01)the Research Fund of Tsinghua University(2011Z05117)the Co-innovation Laboratory of Aerospace Broadband Network Technology
文摘Due to the limited transmission resources for data relay in the tracking and data relay satellite system （TDRSS）, there are many job requirements in busy days which will be discarded in the conventional job scheduling model. Therefore, the improvement of scheduling efficiency in the TDRSS can not only help to increase the resource utilities, but also to reduce the scheduling failure ratio. A model of nonhomogeneous parallel machines scheduling problems with time window （NPM-TW） is firstly built up for the TDRSS, considering the distinct features of the variable preparation time and the nonhomogeneous transmission rates for different types of antennas on each tracking and data relay satellite （TDRS）. Then, an adaptive subsequence adjustment （ASA） framework with evolutionary asymmetric path-relinking （EvAPR） is proposed to solve this problem, in which an asymmetric progressive crossover operation is involved to overcome the local optima by the conventional job inserting methods. The numerical results show that, compared with the classical greedy randomized adaptive search procedure （GRASP） algorithm, the scheduling failure ratio of jobs can be reduced over 11% on average by the proposed ASA with EvAPR.
