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]展开更多
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.展开更多
This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph-<span style="font-family:;" "=""> </span&...This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph-<span style="font-family:;" "=""> </span><span style="font-family:Verdana;">based and sequence-based, of the well-known scheduling problem<img src="Edit_41010f25-7ca5-482c-89be-790fad4616e1.png" alt="" /></span><span style="font-family:Verdana;text-align:justify;">. Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.</span> <div> <span style="font-family:Verdana;text-align:justify;"><br /> </span> </div>展开更多
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.展开更多
针对制造行业中广泛存在的一类复杂并行机调度问题,即带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with arrival time, multiple operations, process restraints and sequence...针对制造行业中广泛存在的一类复杂并行机调度问题,即带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with arrival time, multiple operations, process restraints and sequencedependent setup times, PMSP AMPS),建立问题的排序模型并提出一种混合离散教与学优化算法进行求解,优化目标为最小化最大完工时间.首先,根据标准教与学算法(Teaching-learning-based optimization, TLBO)中两阶段个体更新公式的特点,在保留每一阶段个体更新公式框架不变的前提下,对公式中具体改变实数个体或向量的每个核心操作均用所设计的排列操作进行替换,使其可直接在离散问题解空间中执行基于标准教与学算法机理的全局搜索,从而明显提高了原算法的全局搜索效率.其次,采用交换操作和插入操作构造了一种简洁有效地变邻域局部搜索,对全局搜索发现的优质解区域进行细致搜索,从而进一步增强了算法的性能.通过对不同测试问题的仿真实验和算法比较,验证了所提算法可有效求解PMSP AMPS.展开更多
文摘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]
文摘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.
文摘This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph-<span style="font-family:;" "=""> </span><span style="font-family:Verdana;">based and sequence-based, of the well-known scheduling problem<img src="Edit_41010f25-7ca5-482c-89be-790fad4616e1.png" alt="" /></span><span style="font-family:Verdana;text-align:justify;">. Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.</span> <div> <span style="font-family:Verdana;text-align:justify;"><br /> </span> </div>
文摘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.
文摘针对制造行业中广泛存在的一类复杂并行机调度问题,即带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with arrival time, multiple operations, process restraints and sequencedependent setup times, PMSP AMPS),建立问题的排序模型并提出一种混合离散教与学优化算法进行求解,优化目标为最小化最大完工时间.首先,根据标准教与学算法(Teaching-learning-based optimization, TLBO)中两阶段个体更新公式的特点,在保留每一阶段个体更新公式框架不变的前提下,对公式中具体改变实数个体或向量的每个核心操作均用所设计的排列操作进行替换,使其可直接在离散问题解空间中执行基于标准教与学算法机理的全局搜索,从而明显提高了原算法的全局搜索效率.其次,采用交换操作和插入操作构造了一种简洁有效地变邻域局部搜索,对全局搜索发现的优质解区域进行细致搜索,从而进一步增强了算法的性能.通过对不同测试问题的仿真实验和算法比较,验证了所提算法可有效求解PMSP AMPS.
