一种基于支持向量域描述的区间数分类

研究了基于数据的区间数智能决策分析,提出了一种基于区间数的支持向量域多分类软计算方法,该方法可以直接处理特征空间为区间数的多分类问题,拓展了支持向量域多分类算法应用的范围.     

分类讨论法在初中数学解题中的有效应用

分类讨论的方法对确保学生回答问题的完整性具有重要帮助.本文将从“按数分类讨论”“按字母的取值范围分类讨论”“按图形的位置特征分类讨论”三个方面对分类讨论法在解题教学中的有效应用进行讨论.     

高考专题复习系列讲座——排列、组合和概率

[考试内容和考试要求]1.排列、组合、二项式定理考试内容:分类计数原理与分步计数原理,排列,排列数公式,组合,组合数公式,组合数的两个性质,二项式定理,二项展开式的性质.考试要求:1)掌握分类计数原理与分步计数原理,并能用它们分析和解决一些简单的应用问题.2)理解排列的意义,     

从染色问题谈两个计数原理的教学

分类加法计数原理与分步乘法计数原理是解排列组合问题和后续的概率统计问题的重要基础.这两个基本原理可简述为:完成一件事有几种不同方案,那么完成这件事的不同方法数只须将几种不同方案的方法数相加--即分类加法计数原理;完成一件事需要几个步骤,那么完成这件事的不同方法数只要将这几个步骤的方法数相乘--即分步乘法计数原理.……     

学会分类讨论

同学们知道,分类讨论是数学中的重要思想方法,也是解决问题的常见策略.但是,在教学中发现,有些同学囿于分类讨论意识淡漠,对分类标准疏于把握,或对讨论过程简化不够,以至于在运用分类讨论审视问题时,常常出现一些不应有的失误.有感于此,本文就如何正确地运用分类讨论解决问题,给同学们提出三点建议,供参考.其一、树立分类思想在数学中,某些定义、性质、公式的本身就涉及到分门别类的问题,如实数a的绝对值     

含参数问题的分类与讨论

同一个数学问题有时含有多种情况,对多 种情况加以分类,并逐步求解,这就是分类讨 论法.掌握分类讨论的思考方法,不仅是学好 数学的需要,也是学好其它各门功课的需要. 分类讨论首先要明确分类的原因(即为什 么要分类).引起分类讨论的原因很多,常见的 有:某些数学概念本身是分类定义的;数学问     

完备Leibniz代数的性质及其低维分类

本文研究了完备Leibniz代数的性质及低维分类.利用Leibniz代数中平方元生成的双边理想,获得了小于五维的完备Leibniz代数完整的分类,以及五维时一类特殊情况下完备Leibniz代数的分类,从而推广了Leibniz代数的结构理论.     

提高思维素质 发展创新意识——例说代数问题的图形解证法

华罗庚教授曾指出:“数无形时少直观,形无数时难入微.”对较抽象的代数问题,我们不妨根据已知条件及其内涵,构造图形,借形论数,直观地阐明数之间的某种关系,使较抽象的代数问题明朗化、简单化.从而,创造性地获得巧解妙证.现分类例举如下,以供探究.     

模糊数空间上的积分度量及其在模糊聚类中的应用

在本文中,首先利用区间数的EW-型度量探讨了模糊数空间上的积分度量问题,给出了模糊数空间上的一种新的积分度量-EW-型积分度量,并证明了其相关性质.其次,作为EW-型积分度量的应用,设计了对属性特征为三角模糊数的事物进行分类的模糊聚类算法.然后通过实例分析,说明了EW-型积分度量使模糊聚类算法实现的更简单易行,分类更加精细,合理有效等。     

Rees矩阵半群的GK-维数（英文）

主要探讨Rees矩阵半群的GK-维数问题.首先刻画Rees矩阵半群的性质,含有零元的一类Rees矩阵半群S的GK-维数等于S的任意非零极大幺半群M的GK-维数.然后利用这些性质,证明一类Rees矩阵半群S有多项式增长当且仅当S的所有的子幺半群有多项式增长,推广了本原富足半群里的相关结果.     

Scheduling with batch setup times and earliness-tardiness penalties

We consider a scheduling model in which several batches of jobs need to be processed by a single machine. During processing, a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. All the jobs in the same batch have a common due date that is either externally given as an input data or internally determined as a decision variable. Two problems are investigated. One problem is to minimize the total earliness and tardiness penalties provided that each due date is externally given. We show that this problem is NP-hard even when there are only two batches of jobs and the two due dates are unrestrictively large. The other problem is to minimize the total earliness and tardiness penalties plus the total due date penalty provided that each due date is a decision variable. We give some optimality properties for this problem with the general case and propose a polynomial dynamic programming algorithm for solving this problem with two batches of jobs. We also consider a special case for both of the problems when the common due dates for different batches are all equal. Under this special case, we give a dynamic programming algorithm for solving the first problem with an unrestrictively large due date and for solving the second problem. This algorithm has a running time polynomial in the number of jobs but exponential in the number of batches.     

Fuzzy scheduling of job orders in a two-stage flowshop with batch-processing machines

In this paper, we present a mixed-integer fuzzy programming model and a genetic algorithm (GA) based solution approach to a scheduling problem of customer orders in a mass customizing furniture industry. Independent job orders are grouped into multiple classes based on similarity in style so that the required number of setups is minimized. The family of jobs can be partitioned into batches, where each batch consists of a set of consecutively processed jobs from the same class. If a batch is assigned to one of available parallel machines, a setup is required at the beginning of the first job in that batch. A schedule defines the way how the batches are created from the independent jobs and specifies the processing order of the batches and that of the jobs within the batches. A machine can only process one job at a time, and cannot perform any processing while undergoing a setup. The proposed formulation minimizes the total weighted flowtime while fulfilling due date requirements. The imprecision associated with estimation of setup and processing times are represented by fuzzy sets.     

Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time

We consider the problem of scheduling multi-operation jobs on a singe machine to minimize the total completion time. Each job consists of several operations that belong to different families. In a schedule each family of job operations may be processed as batches with each batch incurring a set-up time. A job is completed when all of its operations have been processed. We first show that the problem is strongly NP-hard even when the set-up times are common and each operation is not missing. When the operations have identical processing times and either the maximum set-up time is sufficiently small or the minimum set-up time is sufficiently large, the problem can be solved in polynomial time. We then consider the problem under the job-batch restriction in which the operations of each batch is partitioned into operation batches according to a partition of the jobs. We show that this case of the problem can be solved in polynomial time under a certain condition.     

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

Single machine batch scheduling with resource dependent setup and processing times

Jobs are processed by a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource, which may be different from that for the jobs. Polynomial time algorithms are presented to find an optimal batch sequence and resource values such that either the total weighted resource consumption is minimized, subject to meeting job deadlines, or the maximum job lateness is minimized, subject to an upper bound on the total weighted resource consumption. The algorithms are based on linear programming formulations of the corresponding problems.     

Fabrication scheduling on a single machine with due date constraints

There is a fabrication machine available for processing a set of jobs. Each job is associated with a due date and consists of two parts, one is common among all products and the other is unique to itself. The unique components are processed individually and the common parts are grouped into batches for processing. A constant setup time is incurred when each batch is formed. The completion time of a job is defined as the time when both of its unique and common components are completed. In this paper, we consider two different objectives. The first problem seeks to minimize the maximum tardiness, and the second problem is to minimize the number of tardy jobs. To minimize the maximum tardiness, we propose a dynamic programming algorithm that optimally solves the problem in polynomial time. Next, we show NP-hardness proof and design a pseudo-polynomial time dynamic programming algorithm for the problem of minimizing the number of tardy jobs.     

Minimizing number of tardy jobs on a batch processing machine with incompatible job families

In this paper we consider the problem of minimizing number of tardy jobs on a single batch processing machine. The batch processing machine is capable of processing up to B jobs simultaneously as a batch. We are given a set of n jobs which can be partitioned into m incompatible families such that the processing times of all jobs belonging to the same family are equal and jobs of different families cannot be processed together. We show that this problem is NP-hard and present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also show that when the jobs of a family have a common due date the problem can be solved by a pseudo-polynomial time procedure.     

Batch scheduling with controllable setup and processing times to minimize total completion time

We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n³ log n) and O(n⁵) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.     

A constraint programming approach for a batch processing problem with non-identical job sizes

This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price.     

Batch Delivery Scheduling on a Single Machine

The problem of partitioning a set of independent and simultaneously available jobs into batches and sequencing them for processing on a single machine is presented. Jobs in the same batch are to be delivered together, upon completion of the last job in the batch. Jobs finished before this time have to wait until delivery. There are a delivery cost depending on the number of batches formed and an earliness cost for jobs finished before delivery. The dynamic programming approach to minimizing the total cost is considered, yielding two pseudopolynomial algorithms when the number of batches has a fixed upper bound. A polynomial algorithm for a special case of the problem is also presented.