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.展开更多
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 problem of minimizing the maximum lateness on a single machine with family setups is considered.To solve the problem, dominance property is studied and then introduced into the tabu search(TS) algorithm.With the...The problem of minimizing the maximum lateness on a single machine with family setups is considered.To solve the problem, dominance property is studied and then introduced into the tabu search(TS) algorithm.With the dominance property, most unpromising neighbors can be excluded from the neighborhood, which makes the search process always focus on the most promising areas of the solution space.The proposed algorithms are tested both on the randomly generated problems and on the real-life problems.Computational results show that the proposed TS algorithm outperforms the best existing algorithm and can solve the real-life problems in about 1.3 on average.展开更多
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.展开更多
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.展开更多
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.展开更多
Severe shield jamming events have been reported during excavation of Uluabat tunnel through adverse geological conditions, which resulted in several stoppages at advancing a single shielded tunnel boring machine(TBM)....Severe shield jamming events have been reported during excavation of Uluabat tunnel through adverse geological conditions, which resulted in several stoppages at advancing a single shielded tunnel boring machine(TBM). To study the jamming mechanism, three-dimensional(3D) simulation of the machine and surrounding ground was implemented using the finite difference code FLAC3D. Numerical analyses were performed for three sections along the tunnel with a higher risk for entrapment due to the combination of overburden and geological conditions. The computational results including longitudinal displacement contours and ground pressure profiles around the shield allow a better understanding of ground behavior within the excavation. Furthermore, they allow realistically assessing the impact of adverse geological conditions on shield jamming. The calculated thrust forces, which are required to move the machine forward, are in good agreement with field observations and measurements. It also proves that the numerical analysis can effectively be used for evaluating the effect of adverse geological environment on TBM entrapments and can be applied to prediction of loads on the shield and preestimating of the required thrust force during excavation through adverse ground conditions.展开更多
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 the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing...In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.展开更多
We consider a scheduling problem involving a single processor utilized by two customers with constant deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. Tradition...We consider a scheduling problem involving a single processor utilized by two customers with constant deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. Traditionally, such scenarios are modeled by assuming that each customer has the same criterion. In practice, this assumption may not hold. Instead of using a single criterion, we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated with their individual criteria. We examine three basic scheduling criteria: minimizing makespan, minimizing maximum lateness, and minimizing total weighted completion time. We demonstrate all the scheduling problems considered are polynomially solvable.展开更多
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.展开更多
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.展开更多
This paper presents a method of dealing with the problem of assigning a due date which can either be known or unknown to a set of simultaneously available jobs and sequencing them on a single machine. The objective...This paper presents a method of dealing with the problem of assigning a due date which can either be known or unknown to a set of simultaneously available jobs and sequencing them on a single machine. The objective is to determine the optimal job sequence when the due date is common and known or to determine an optimal combination of the common due date and job sequence when the due date is unknown that minimizes a cost function. A dynamic programming algorithm of finding the optimal solution to the problem is presented. It is shown that the due date can simply be chosen from the set of marginal points of an interval which is divide within [0,∞] by the sum of every possible combination the job sequences. Finally, an illustrative example is provided.展开更多
nm roughness value of silicon surface by diamond turning is obtained firstly and three novel techniques are proposed. The surface integrity is studied in detail by using atomic force microscope, scanning electron micr...nm roughness value of silicon surface by diamond turning is obtained firstly and three novel techniques are proposed. The surface integrity is studied in detail by using atomic force microscope, scanning electron microscope, and stylus surface instrument. The diamond tool sharpness has a considerable influence on the machined surface, therefore a novel technique—brightness modulation for measuring accurately the edge of the cutter is proposed. Mirror surfaces are assessed by another novel technique—a measure of their reflectivity. A third technique, single grit diamond machining is carried out. It supplies a experimental evidence for verifying the obtained high quality turned surfaces.展开更多
This paper deals with single-machine scheduling problems with a more general learning effect based on sum-of-processing-time. In this study, sum-of-processing-time-based learning effect means that the processing time ...This paper deals with single-machine scheduling problems with a more general learning effect based on sum-of-processing-time. In this study, sum-of-processing-time-based learning effect means that the processing time of a job is defined by a decreasing function of the total normal processing time of jobs that come before it in the sequence. Results show that even with the introduction of the sum-of-processing-time-based learning effect to job processing times, single-machine makespan minimization problems remain polynomially solvable. The curves of the optimal schedule of a total completion time minimization problem are V-shaped with respect to iob normal orocessinz times.展开更多
A whale optimization algorithm(WOA)-based power system stabilizer(PSS)design methodology on modified single machine infinite bus(MSMIB)and multi-machine systems to enhance the small-signal stability(SSS)of the power s...A whale optimization algorithm(WOA)-based power system stabilizer(PSS)design methodology on modified single machine infinite bus(MSMIB)and multi-machine systems to enhance the small-signal stability(SSS)of the power system is presented.The PSS design methodology is implemented using an eigenvalue(EV)-based objective function.The performance of the WOA is tested with several CEC14 and CEC17 test functions to investigate its potential in optimizing the complex mathematical equations.The New England 10-generator 39-bus system and the MSMIB system operating at various loading conditions are considered as the test systems to examine the proposed method.Extensive simulation results are obtained which validate the effectiveness of the proposed WOA method when compared with other algorithms.展开更多
Scheduling with group technology has been a vivid research area in the past decades.However,group technology with general dual-effect variable processing times needs to be further explored although this kind of group...Scheduling with group technology has been a vivid research area in the past decades.However,group technology with general dual-effect variable processing times needs to be further explored although this kind of group technology plays an important role in some actual manufacturing scenarios.Accordingly,this paper considers group scheduling problems with a kind of general group variable processing times model,where the actual processing time of each job in group is variable due to the dual effect of both the job position and the group position.The objectives of two types of considered problems are to minimize the makespan and the total completion time,respectively.Based on the decomposition analysis,the mathematical logic analysis and the computational complexity proof,it is obtained that the makespan minimization problem and the total completion time minimization problem are both polynomially solvable under the condition that the group number is constant.For three special cases of considered problems,polynomial solving algorithms with lower computational complexity are proposed.展开更多
基金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.
文摘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 Major State Basic Research Development Program of China (973 Program)(2002CB312205)the National Natural Science Foundation of China (60574077+2 种基金 60874071 60834004)the National High Technology Research and Development Program of China (863 Program) (2007AA04Z102)
文摘The problem of minimizing the maximum lateness on a single machine with family setups is considered.To solve the problem, dominance property is studied and then introduced into the tabu search(TS) algorithm.With the dominance property, most unpromising neighbors can be excluded from the neighborhood, which makes the search process always focus on the most promising areas of the solution space.The proposed algorithms are tested both on the randomly generated problems and on the real-life problems.Computational results show that the proposed TS algorithm outperforms the best existing algorithm and can solve the real-life problems in about 1.3 on average.
文摘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.
文摘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.
文摘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.
基金Alexander von Humboldt-Foundation (AvH) for the financial support as a research fellowthe financial support of the Scientific and Technological Research Council of Turkey (TüB_ITAK) under Project No. MAG-114M568
文摘Severe shield jamming events have been reported during excavation of Uluabat tunnel through adverse geological conditions, which resulted in several stoppages at advancing a single shielded tunnel boring machine(TBM). To study the jamming mechanism, three-dimensional(3D) simulation of the machine and surrounding ground was implemented using the finite difference code FLAC3D. Numerical analyses were performed for three sections along the tunnel with a higher risk for entrapment due to the combination of overburden and geological conditions. The computational results including longitudinal displacement contours and ground pressure profiles around the shield allow a better understanding of ground behavior within the excavation. Furthermore, they allow realistically assessing the impact of adverse geological conditions on shield jamming. The calculated thrust forces, which are required to move the machine forward, are in good agreement with field observations and measurements. It also proves that the numerical analysis can effectively be used for evaluating the effect of adverse geological environment on TBM entrapments and can be applied to prediction of loads on the shield and preestimating of the required thrust force during excavation through adverse ground conditions.
基金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.
基金Supported by the National Natural Science Foundation of China(11271338, 11201121, 71201049) Supported by the National Natural Science Foundation of Henan Province(112300410078) Supported by the Natural Science Foundation of the Education Department of Henan Province(2011B110008)
文摘In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.
文摘We consider a scheduling problem involving a single processor utilized by two customers with constant deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. Traditionally, such scenarios are modeled by assuming that each customer has the same criterion. In practice, this assumption may not hold. Instead of using a single criterion, we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated with their individual criteria. We examine three basic scheduling criteria: minimizing makespan, minimizing maximum lateness, and minimizing total weighted completion time. We demonstrate all the scheduling problems considered are polynomially solvable.
文摘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.
基金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.
文摘This paper presents a method of dealing with the problem of assigning a due date which can either be known or unknown to a set of simultaneously available jobs and sequencing them on a single machine. The objective is to determine the optimal job sequence when the due date is common and known or to determine an optimal combination of the common due date and job sequence when the due date is unknown that minimizes a cost function. A dynamic programming algorithm of finding the optimal solution to the problem is presented. It is shown that the due date can simply be chosen from the set of marginal points of an interval which is divide within [0,∞] by the sum of every possible combination the job sequences. Finally, an illustrative example is provided.
文摘nm roughness value of silicon surface by diamond turning is obtained firstly and three novel techniques are proposed. The surface integrity is studied in detail by using atomic force microscope, scanning electron microscope, and stylus surface instrument. The diamond tool sharpness has a considerable influence on the machined surface, therefore a novel technique—brightness modulation for measuring accurately the edge of the cutter is proposed. Mirror surfaces are assessed by another novel technique—a measure of their reflectivity. A third technique, single grit diamond machining is carried out. It supplies a experimental evidence for verifying the obtained high quality turned surfaces.
文摘This paper deals with single-machine scheduling problems with a more general learning effect based on sum-of-processing-time. In this study, sum-of-processing-time-based learning effect means that the processing time of a job is defined by a decreasing function of the total normal processing time of jobs that come before it in the sequence. Results show that even with the introduction of the sum-of-processing-time-based learning effect to job processing times, single-machine makespan minimization problems remain polynomially solvable. The curves of the optimal schedule of a total completion time minimization problem are V-shaped with respect to iob normal orocessinz times.
文摘A whale optimization algorithm(WOA)-based power system stabilizer(PSS)design methodology on modified single machine infinite bus(MSMIB)and multi-machine systems to enhance the small-signal stability(SSS)of the power system is presented.The PSS design methodology is implemented using an eigenvalue(EV)-based objective function.The performance of the WOA is tested with several CEC14 and CEC17 test functions to investigate its potential in optimizing the complex mathematical equations.The New England 10-generator 39-bus system and the MSMIB system operating at various loading conditions are considered as the test systems to examine the proposed method.Extensive simulation results are obtained which validate the effectiveness of the proposed WOA method when compared with other algorithms.
基金the National Natural Science Foundation of China(No.71573121)China Postdoctoral Science Foundation Funded Project(No.2016M590453)the Fundamental Research Funds for the Central Universities(Nos.NS2016080 and NR2016005).
文摘Scheduling with group technology has been a vivid research area in the past decades.However,group technology with general dual-effect variable processing times needs to be further explored although this kind of group technology plays an important role in some actual manufacturing scenarios.Accordingly,this paper considers group scheduling problems with a kind of general group variable processing times model,where the actual processing time of each job in group is variable due to the dual effect of both the job position and the group position.The objectives of two types of considered problems are to minimize the makespan and the total completion time,respectively.Based on the decomposition analysis,the mathematical logic analysis and the computational complexity proof,it is obtained that the makespan minimization problem and the total completion time minimization problem are both polynomially solvable under the condition that the group number is constant.For three special cases of considered problems,polynomial solving algorithms with lower computational complexity are proposed.