Focusing on the single machine scheduling problem which minimizes the total completion time in the presence of dynamic job arrivals, a rolling optimization scheduling algorithm is proposed based on the analysis of the...Focusing on the single machine scheduling problem which minimizes the total completion time in the presence of dynamic job arrivals, a rolling optimization scheduling algorithm is proposed based on the analysis of the character and structure of scheduling. An optimal scheduling strategy in collision window is presented. Performance evaluation of this algorithm is given. Simulation indicates that the proposed algorithm is better than other common heuristic algorithms on both the total performance and stability.展开更多
The single machine scheduling problem which involves uncertain job due dates is one of the most important issues in the real make-to-order environment. To deal with the uncertainty, this paper establishes a robust opt...The single machine scheduling problem which involves uncertain job due dates is one of the most important issues in the real make-to-order environment. To deal with the uncertainty, this paper establishes a robust optimization model by minimizing the maximum tardiness in the worst case scenario over all jobs. Unlike the traditional stochastic programming model which requires exact distributions, our model only needs the information of due date intervals. The worst case scenario for a given sequence that belongs to a set containing only n scenarios is proved, where n is the number of jobs. Then, the model is simplified and reformulated as an equivalent mixed 0-1 integer linear programming(MILP) problem. To solve the MILP problems efficiently, a heuristic approach is proposed based on a robust dominance rule. The experimental results show that the proposed method has the advantages of robustness and high calculating efficiency, and it is feasible for large-scale problems.展开更多
Considering the independent optimization requirement for each demander of modernmanufacture, we explore the application of noncooperative game in production scheduling research,and model scheduling problem as competit...Considering the independent optimization requirement for each demander of modernmanufacture, we explore the application of noncooperative game in production scheduling research,and model scheduling problem as competition of machine resources among a group of selfish jobs.Each job has its own performance objective. For the single machine, multi-jobs and non-preemptivescheduling problem, a noncooperative game model is established. Based on the model, many prob-lems about Nash equilibrium solution, such as the existence, quantity, properties of solution space,performance of solution and algorithm are discussed. The results are tested by numerical example.展开更多
We study the classical single machine scheduling problem but with uncertainty. A robust optimization model is presented, and an effective deep cut is derived. Numerical experiments show effectiveness of the derived cut.
The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved ...The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved by 3 partition problem that if the problem is of ready time and common deadline constrained, its complexity is NP hard in the strong sense. Finally, a polynomial algorithm for solving unit processing time and common deadline problems is proposed.展开更多
In this paper, single machine scheduling problems with variable processing time are raised. The criterions of the problem considered are minimizing scheduling length of all jobs, flow time and number of tardy jobs and...In this paper, single machine scheduling problems with variable processing time are raised. The criterions of the problem considered are minimizing scheduling length of all jobs, flow time and number of tardy jobs and so on. The complexity of the problem is determined. [WT5HZ]展开更多
In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' ...In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' of the job on position i and a “normal' processing time of the job. The criteria considered is to minimize scheduled length of all jobs. A lemma is proposed and proved. In no deadline constrained condition, the problem belongs to polynomial time algorithm. It is proved by using 3 partition that if the problem is deadline constrained, its complexity is strong NP hard. Finally, a conjuncture is proposed that is to be proved.展开更多
It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling proble...It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.展开更多
In this paper, by considering the fuzzy nature of the data in real-life problems, single machine scheduling problems with fuzzy processing time and multiple objectives are formulated and an efficient genetic algorithm...In this paper, by considering the fuzzy nature of the data in real-life problems, single machine scheduling problems with fuzzy processing time and multiple objectives are formulated and an efficient genetic algorithm which is suitable for solving these problems is proposed. As illustrative numerical examples, twenty jobs processing on a machine is considered. The feasibility and effectiveness of the proposed method have been demonstrated in the simulation.展开更多
In this paper,single machine scheduling problems with variable processing time areraised.The criterions of the prolem considered are minimizing scheduling length of all jobs,flowtime and number of tardy jobs and so on...In this paper,single machine scheduling problems with variable processing time areraised.The criterions of the prolem considered are minimizing scheduling length of all jobs,flowtime and number of tardy jobs and so on.The complexity of the problem is determined.展开更多
In this study,an optimization model of a single machine system integrating imperfect preventive maintenance planning and production scheduling based on game theory is proposed.The costs of the production department an...In this study,an optimization model of a single machine system integrating imperfect preventive maintenance planning and production scheduling based on game theory is proposed.The costs of the production department and the maintenance department are minimized,respectively.Two kinds of three-stage dynamic game models and a backward induction method are proposed to determine the preventive maintenance(PM)threshold.A lemma is presented to obtain the exact solution.A comprehensive numerical study is provided to illustrate the proposed maintenance model.The effectiveness is also validated by comparison with other two existed optimization models.展开更多
In a recent paper,Feng et al.[5](Two-agent scheduling with rejection on a single machine.Appl.Math.Model.39(2015)1183-1193)studied some two-agent scheduling problems with rejection on a single machine.The authors show...In a recent paper,Feng et al.[5](Two-agent scheduling with rejection on a single machine.Appl.Math.Model.39(2015)1183-1193)studied some two-agent scheduling problems with rejection on a single machine.The authors showed that all problems are NP-hard and then provided four dynamic programming algorithms.Unfortunately,we observe that some mistakes are contained in the two dynamic programming algorithms.In this note,we first show by a counter-example that the above two algorithms are incorrect.Furthermore,we also provide two new dynamic programming algorithms to solve the same problems.展开更多
Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu- ally independent and available at time zero.The machine processes the jobs sequentially and it is not i...Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu- ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro- cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs’completion time.While the sum of jobs’processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul- ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im- proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc- ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.展开更多
Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz＇ s branch and bound scheme ...Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz＇ s branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.展开更多
This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (V<sub>max</sub>), maximum tardy job, denote...This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (V<sub>max</sub>), maximum tardy job, denoted by (T<sub>max</sub>), and maximum earliness (E<sub>max</sub>). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (V<sub>max</sub>, T<sub>max</sub>, E<sub>max</sub>) and 1//(V<sub>max</sub> + T<sub>max</sub> + E<sub>max</sub>). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.展开更多
In a learning effect environment, the machine improves continuously as a result of repeating the same or similar jobs, hence the later a given job is scheduled in the sequence, the shorter its processing time is. In t...In a learning effect environment, the machine improves continuously as a result of repeating the same or similar jobs, hence the later a given job is scheduled in the sequence, the shorter its processing time is. In this paper, we consider a new general learning effect, i.e. Dejong＇s learning effect. Using this Dejong＇s learning effect polynomial solutions for the single machine makespan minimization problem, total flow time minimization problem and two classes of single machine multi-criteria problems are obtained.展开更多
In this paper, a single-machine scheduling model with a given common due date and simple linear processing times was considered. The objective is the total weighted tardiness penalty and earliness award. Some polynomi...In this paper, a single-machine scheduling model with a given common due date and simple linear processing times was considered. The objective is the total weighted tardiness penalty and earliness award. Some polynomial time solvable cases for this problem are given. A dynamic programming algorithm was provided and a branch and bound algorithm for general case of the problem was provided based on a rapid method for estimating the lower bound.展开更多
In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total we...In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided.展开更多
This paper gives the sensitivity analysis for some scheduling problems, including the following： what are the limits to a parameter change such that the solution remain optimal？ Given a specific change of a paramete...This paper gives the sensitivity analysis for some scheduling problems, including the following： what are the limits to a parameter change such that the solution remain optimal？ Given a specific change of a parameter, what is the new optimal cost？ Given a specific change of a parameter, what is a new optimal solution？ Here, the concern is mainly with the sensitivity analysis for some single-machine and flowshop scheduling problems with polynomial time algorithms. It is shown that, for these problems, the sensitivity analysis results depend on the positions of jobs with changed parameters.展开更多
文摘Focusing on the single machine scheduling problem which minimizes the total completion time in the presence of dynamic job arrivals, a rolling optimization scheduling algorithm is proposed based on the analysis of the character and structure of scheduling. An optimal scheduling strategy in collision window is presented. Performance evaluation of this algorithm is given. Simulation indicates that the proposed algorithm is better than other common heuristic algorithms on both the total performance and stability.
基金supported by the National Natural Science Foundation of China(61503211,U1660202)。
文摘The single machine scheduling problem which involves uncertain job due dates is one of the most important issues in the real make-to-order environment. To deal with the uncertainty, this paper establishes a robust optimization model by minimizing the maximum tardiness in the worst case scenario over all jobs. Unlike the traditional stochastic programming model which requires exact distributions, our model only needs the information of due date intervals. The worst case scenario for a given sequence that belongs to a set containing only n scenarios is proved, where n is the number of jobs. Then, the model is simplified and reformulated as an equivalent mixed 0-1 integer linear programming(MILP) problem. To solve the MILP problems efficiently, a heuristic approach is proposed based on a robust dominance rule. The experimental results show that the proposed method has the advantages of robustness and high calculating efficiency, and it is feasible for large-scale problems.
基金Supported by the State Key Program of National Natural Science of China（70931001）, the Science Fund for Creative Research Group of National Natural Science Foundation of China （60821063）, National Science and Technology Support Plan of China （2006BAH02A09）, the Science Fund for Youth Scholars of Ministry of Education of China （200801451053）, and the Research Committee and the Department of Industrial and Systems Engineering of Hong Kong Polytechnic University Research Grants （G-U323）
文摘Considering the independent optimization requirement for each demander of modernmanufacture, we explore the application of noncooperative game in production scheduling research,and model scheduling problem as competition of machine resources among a group of selfish jobs.Each job has its own performance objective. For the single machine, multi-jobs and non-preemptivescheduling problem, a noncooperative game model is established. Based on the model, many prob-lems about Nash equilibrium solution, such as the existence, quantity, properties of solution space,performance of solution and algorithm are discussed. The results are tested by numerical example.
文摘We study the classical single machine scheduling problem but with uncertainty. A robust optimization model is presented, and an effective deep cut is derived. Numerical experiments show effectiveness of the derived cut.
文摘The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved by 3 partition problem that if the problem is of ready time and common deadline constrained, its complexity is NP hard in the strong sense. Finally, a polynomial algorithm for solving unit processing time and common deadline problems is proposed.
文摘In this paper, single machine scheduling problems with variable processing time are raised. The criterions of the problem considered are minimizing scheduling length of all jobs, flow time and number of tardy jobs and so on. The complexity of the problem is determined. [WT5HZ]
文摘In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' of the job on position i and a “normal' processing time of the job. The criteria considered is to minimize scheduled length of all jobs. A lemma is proposed and proved. In no deadline constrained condition, the problem belongs to polynomial time algorithm. It is proved by using 3 partition that if the problem is deadline constrained, its complexity is strong NP hard. Finally, a conjuncture is proposed that is to be proved.
文摘It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.
基金supported by the National Natural Science Foundation of China(NNSFC)(the grant No.60274043)supported by the National High-tech Research&Development Project(863)(the grant No.2002AA412610)
文摘In this paper, by considering the fuzzy nature of the data in real-life problems, single machine scheduling problems with fuzzy processing time and multiple objectives are formulated and an efficient genetic algorithm which is suitable for solving these problems is proposed. As illustrative numerical examples, twenty jobs processing on a machine is considered. The feasibility and effectiveness of the proposed method have been demonstrated in the simulation.
基金Supported by National Postdoctoral Science Foundation of P.R.China(9902)
文摘In this paper,single machine scheduling problems with variable processing time areraised.The criterions of the prolem considered are minimizing scheduling length of all jobs,flowtime and number of tardy jobs and so on.The complexity of the problem is determined.
基金Sponsored by the National Natural Science Foundation of China(Grant Nos.72061022 and 72171037).
文摘In this study,an optimization model of a single machine system integrating imperfect preventive maintenance planning and production scheduling based on game theory is proposed.The costs of the production department and the maintenance department are minimized,respectively.Two kinds of three-stage dynamic game models and a backward induction method are proposed to determine the preventive maintenance(PM)threshold.A lemma is presented to obtain the exact solution.A comprehensive numerical study is provided to illustrate the proposed maintenance model.The effectiveness is also validated by comparison with other two existed optimization models.
基金Supported by National Natural Science Foundation of China(Grant Nos.11901168,11971443 and 12271491)。
文摘In a recent paper,Feng et al.[5](Two-agent scheduling with rejection on a single machine.Appl.Math.Model.39(2015)1183-1193)studied some two-agent scheduling problems with rejection on a single machine.The authors showed that all problems are NP-hard and then provided four dynamic programming algorithms.Unfortunately,we observe that some mistakes are contained in the two dynamic programming algorithms.In this note,we first show by a counter-example that the above two algorithms are incorrect.Furthermore,we also provide two new dynamic programming algorithms to solve the same problems.
文摘Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu- ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro- cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs’completion time.While the sum of jobs’processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul- ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im- proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc- ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.
文摘Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz＇ s branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.
文摘This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (V<sub>max</sub>), maximum tardy job, denoted by (T<sub>max</sub>), and maximum earliness (E<sub>max</sub>). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (V<sub>max</sub>, T<sub>max</sub>, E<sub>max</sub>) and 1//(V<sub>max</sub> + T<sub>max</sub> + E<sub>max</sub>). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.
基金Tianyuan Grant from National Natural Science Foundations (10426008)National Science Foundation of China (10001007)Foundation of Shenyang Institute of Aeronautial Engineering (05YB08)
文摘In a learning effect environment, the machine improves continuously as a result of repeating the same or similar jobs, hence the later a given job is scheduled in the sequence, the shorter its processing time is. In this paper, we consider a new general learning effect, i.e. Dejong＇s learning effect. Using this Dejong＇s learning effect polynomial solutions for the single machine makespan minimization problem, total flow time minimization problem and two classes of single machine multi-criteria problems are obtained.
基金supported by the National Natural Science Foundation of China (Grant No.19771057)
文摘In this paper, a single-machine scheduling model with a given common due date and simple linear processing times was considered. The objective is the total weighted tardiness penalty and earliness award. Some polynomial time solvable cases for this problem are given. A dynamic programming algorithm was provided and a branch and bound algorithm for general case of the problem was provided based on a rapid method for estimating the lower bound.
文摘In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided.
文摘This paper gives the sensitivity analysis for some scheduling problems, including the following： what are the limits to a parameter change such that the solution remain optimal？ Given a specific change of a parameter, what is the new optimal cost？ Given a specific change of a parameter, what is a new optimal solution？ Here, the concern is mainly with the sensitivity analysis for some single-machine and flowshop scheduling problems with polynomial time algorithms. It is shown that, for these problems, the sensitivity analysis results depend on the positions of jobs with changed parameters.
