面向成套订单问题的工艺规划与排序的集成研究

本文从工艺规划与排序的集成优化角度研究了成套订单问题^[1],克服了单独研究工艺规划和排序局部优化的局限性.文章中考虑了同一工件内部各道工序之间存在的优先加工限制,以及工件在不同机器上加工需要转移时间和工序间接连加工需要机器调整时间的情况,建立了成套订单问题的集成排序模型,并提出了针对求解大规模问题的基于遗传算法的启发式算法,最后通过一个算例对所研究的集成排序问题和所提出的算法进行了说明,计算结果表明了算法的有效性.     

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。     

考虑加工与运输协同调度的单机排序问题

在考虑加工与运输协同调度的单机排序问题中,每个工件尺寸不同,工件在一台机器加工后,由m辆有容量限制的运输工具运送到同一个顾客处,目标是极小化最后一个送到其顾客的工件的到达时间,本文给出了该问题的一个最优算法,并且证明了该算法的最坏情况界为3/2。     

一种改进的加权最小二乘排序方法

本文对层次分析法中权的最小平方排序方法^[1-2]进行了改进,提出一种新的改进的加权最小二乘排序方法,并从理论上进行证明。文章最后通过一个实例将两种排序方法与特征根排序方法进行了对比分析,结果表明,改进的加权最小二乘排序方法可导得与特征向量排序方法相同的排序结果,克服了权的最小平方排序方法与特征向量排序方法排序结果不一致的缺点。     

OBE教育理念下高校应用型本科秘书学专业课程体系的构建

<正>2012年秘书学正式列入教育部本科目录，秘书学本科专业课程体系的设置开始进入人们的研究视野。自2013年起，一批学者如石恪^[1]、郑美平^[2]、李志瑾^[3]、蔡茂^[4]、杨志兰^[5]、高凯山^[6]等针对秘书学本科专业课程体系存在的问题提出了有益建议，然而极少有人提及基于OBE教育理念的课程体系建设。而以“学生中心、产出导向、     

加工能力受限的单机干扰管理研究

针对单机环境下最小化加权折扣加工时间和的排序问题,研究如何应对可预见的干扰事件。由于干扰事件使得机器加工能力受限,初始最优加工时间表不再可行,采用外包的方式来进行干扰管理。构建了排序模型,同时考虑原目标和与初始计划偏离的扰动目标,选择外包工件集并对所有工件进行重排序。为了求解得到的双目标排序问题,基于理想点法设计了一种动态规划算法和量子遗传算法相结合的算法。最后通过一个数值算例说明,该排序模型对于求解加工能力受限的单机干扰管理问题是有效的。     

漂移型线性规划理论及应用

到目前为止,有关灰色线性规划问题有不少研究,如灰色预测型线性规划^[1～6]灰色区间型线性规划^[7]等．本文在文献^[1～7]的基础上,针对漂移型线性规划问题,运用参数线性规划理论与方法,对其满意解及其性质等进行探研,并提出了一些新的结论,不仅为漂移型线性规划作了一些理论讨论,而且还以应用实例给予示范．     

重庆市非道路移动源大气污染物排放清单研究

本文通过对非道路移动源的保有量构成和活动水平进行调研分析,采用排放因子法估算并建立了重庆市2018年非道路移动源大气污染物排放清单。结果表明,非道路移动源PM₁₀、PM_2.5、HC、NO_X和CO的排放量分别为9.40×10³ t、8.94×10³ t、1.99×10⁴ t、1.28×10⁵ t和8.06×10⁴ t。船舶为PM₁₀和PM_2.5的最大贡献源,分别占该类污染物排放总量的45.4%和45.7%;工程机械为HC、NO_X和CO的最大贡献源,分别占该类污染物总量的47.7%、42.5%和46.5%。结果同时表明,机械保有量和单机功率对机械污染物的排放量起着重要作用。     

三台平行机排序的一个复合半在线问题的算法

本文讨论一个三台平行机半在线排序问题.对预先知道工件的总加工时间和最大的工件的加工时间的复合半在线模型,我们证明了不存在半在线算法,其竞争比为4/3,并给出了一个竞争比为7/5的半在线算法,两者的差距小于0.067.     

加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。     

Batch-Processing Scheduling with Setup Times

The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.     

On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time

Scheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times C _j is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time w _j C _j. We provide a linear time on-line algorithm for the unrestrictive model (i.e., b n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + )-competitive on-line algorithm for any > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.     

混合离散差分进化算法在单机批处理调度中的应用

本文研究单机批处理调度问题,批处理机有批次容量限制,批处理时间由每个批次所含作业中的最长作业处理时间决定。每个作业具有不同的大小、处理时间、提前拖期惩罚权重,所有作业具有公共交货期,且交货期无限晚。目标函数为最小化所有作业的加权提前拖期惩罚之和。该问题已被证明为NP难题,本研究找到了其最优解具有的一些性质,在此基础上利用它们提出了一种动态规划(DP)与差分进化(DE)算法相结合的混合离散差分进化(HDDE)算法来求解该问题,通过与传统的遗传算法、模拟退火算法和迭代贪婪算法进行对比,HDDE算法显示了更加强大的全局搜索能力。     

Scheduling a single semi-continuous batching machine

This paper addresses a new problem, called semi-continuous batch scheduling, which arises in the heating-operation of tube-billets in the steel industry. Each heating furnace can be regarded as a semi-continuous batching machine, which can handle up to C jobs simultaneously. The jobs in the same batch enter and leave the machine semi-continuously, which differs from the traditional batching machine scheduling where the jobs in same batch have a starting time and a finishing time. In this paper the processing time of a batch depends on the capacity of the semi-continuous batching machine, the longest processing time of jobs in the batch and its size. The objectives are to schedule jobs on the machine so that the makespan and the total completion time are minimized. A schedule for a semi-continuous batching machine consists of a batching and sequencing for the batches. We propose the optimal properties of two different objective functions and present the different dynamic programming algorithms with a running time of O(n²), respectively.     

An optimal online algorithm for single machine scheduling to minimize total general completion time

We study the online problem of single machine scheduling to minimize total general completion time. General completion time is defined as C^a_j=(C_j)^aC^{\alpha}_{j}=(C_{j})^{\alpha}, where C _j denotes the completion time of job J _j and α≥1 is a constant integer. Total general completion time characterizes the feather in service that when a customer is served later in time, his dissatisfaction increases in a manner of power function. The objective function ∑(C _j ) ^α can also be viewed as a total weighted completion time, but the “weight” is no longer a constant number. Our purpose to minimize customers’ total dissatisfaction. The problem is online in the sense that all jobs arrive over time. Each job’s processing time becomes known at its arrival time. Preemption is not allowed. For this online problem, we show that a lower bound on competitive ratio is 2 ^α and prove that D-SPT (delayed shortest processing time) algorithm is optimal with a competitive ratio 2 ^α .     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.     

A FRAMEWORK FOR MACHINE SCHEDULING PROBLEMS WITH CONTROLLABLE PROCESSING TIMES

This is a study of single and parallel machine scheduling problems with controllable processing time for each job. The processing time for job j depends on the position of the job in the schedule and is a function of the number of resource units allocated to its processing. Processing time functions and processing cost functions are allowed to be nonlinear. The scheduling problems considered here have important applications in industry and include many of the existing scheduling models as special cases. For the single machine problem, the objective is minimization of total compression costs plus a scheduling measure. The scheduling measures include makespan, total flow time, total differences in completion times, total differences in waiting times, and total earliness and tardiness with a common due date for all jobs. Except when the total earliness and tardiness measure is involved, each case the problem is solved efficiently. Under an assumption typically satisfied in just-in-time systems, the problem with total earliness and tardiness measure is also solved efficiently. Finally, for a large class of processing time functions; parallel machine problems with total flow time and total earliness and tardiness measures are solved efficiently. In each case we reduce the problem to a transportation problem.     

A note on special optimal batching structures to minimize total weighted completion time

A batch is a subset of jobs which must be processed jointly in either serial or parallel form. The algorithmic aspects of the batching scheduling problems have been extensively studied in the literature. This paper presents necessary and sufficient conditions of the existence of optimal batch sequences for the single machine, batching, total weighted completion time scheduling problems on two batching ways: (1) all jobs form one batch; (2) each batch contains a single job. This kind of conditions can help us to recognize some special optimal schedules quickly. Research supported by NSFC (10671183).     

A bicriteria approach to scheduling a single machine with job rejection and positional penalties

Single machine scheduling problems have been extensively studied in the literature under the assumption that all jobs have to be processed. However, in many practical cases, one may wish to reject the processing of some jobs in the shop, which results in a rejection cost. A solution for a scheduling problem with rejection is given by partitioning the jobs into a set of accepted and a set of rejected jobs, and by scheduling the set of accepted jobs among the machines. The quality of a solution is measured by two criteria: a scheduling criterion, F1, which is dependent on the completion times of the accepted jobs, and the total rejection cost, F2. Problems of scheduling with rejection have been previously studied, but usually within a narrow framework—focusing on one scheduling criterion at a time. This paper provides a robust unified bicriteria analysis of a large set of single machine problems sharing a common property, namely, all problems can be represented by or reduced to a scheduling problem with a scheduling criterion which includes positional penalties. Among these problems are the minimization of the makespan, the sum of completion times, the sum and variation of completion times, and the total earliness plus tardiness costs where the due dates are assignable. Four different problem variations for dealing with the two criteria are studied. The variation of minimizing F1+F2 is shown to be solvable in polynomial time, while all other three variations are shown to be $\mathcal{NP}$ -hard. For those hard problems we provide a pseudo polynomial time algorithm. An FPTAS for obtaining an approximate efficient schedule is provided as well. In addition, we present some interesting special cases which are solvable in polynomial time.