首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献，搜索用时 281 毫秒
1.
This paper considers a reentrant scheduling problem on parallel primary machines with a remote server machine, which is required to carry out the setup operation. In this problem, each job has three operations. The first and last operations are performed by the same primary machine, implying the reentrance, and the second operation is processed on the single server machine. The order of jobs is predetermined in our context. The challenge is to assign jobs to the primary machines to minimize the makespan. We develop a genetic algorithm（GA） to solve this problem. Based on a simple strategy of assigning jobs in batches on the parallel primary machines, the standardized random key vector representation is employed to split the jobs into batches. Comparisons among the proposed algorithm, the branch and bound（BB） algorithm and the heuristic algorithm, coordinated scheduling（CS）, which is only one heuristic algorithm to solve this problem in the literature, are made on the benchmark data. The computational experiments show that the proposed genetic algorithm outperforms the heuristic CS and the maximum relative improvement rate in the makespan is 1.66%.  相似文献   

2.
In this paper,a fabrication scheduling problem concerning the production of components at a single manufacturing facility was studied,in which the manufactured components are subsequently assembled into a finite number of end products. Each product was assumed to comprise a common component to all jobs and a unique component to itself.Common operations were processed in batches and each batch required a setup time.A product is completed when both its two operations have been processed and are available.The optimality criterion considered was the minimization of weighted flow time.For this scheduling problem,the optimal schedules were described in a weignted shortest processing time first(WSPT)order and two algorithms were constructed corresponding to the batch availability and item availability,respectively.  相似文献   

3.
INTRODUCTION Scheduling problems have been studied widely in recent years with many results. In the classical scheduling problems, the processing times of jobs are constant, although, there are many cases where the processing times of jobs are not constant but in- creasing or decreasing over time so that the process- ing times of jobs are no longer independent. For example, a facility is deteriorating because of long time use so that its processing capacity de- creases with time, and a job…  相似文献   

4.
In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two possible widths mj = 1 or m, we present an optimal online algorithm by using ＂temporary schedule＂.  相似文献   

5.
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.  相似文献   

6.
In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fully polynomial time approximation scheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines.  相似文献   

7.
In this paper, a semi on-line version on m identical machines M1 , M2, …, Mm ( m ≥ 3 ) was considered, where the processing time of the largest job is known in advance. Our goal is to maximize the minimum machine load, an NPLS algorithm was presented and its worst-case ratio was proved to be equal to m - 1 which is the best possible value. It is concluded that if the total processing time of jobs is also known to be greater than (2 m - 1 )Pmax where pmax is the largest job‘s processing time, then the worstcase ratio is 2 - 1/m.  相似文献   

8.
A single machine scheduling problem involving fuzzy due dates and fuzzy precedence constraints is investigated. The fuzzy precedence reflects the satisfaction level with respect to precedence between two jobs. A membership function is associated with each job Ji, which describes the degree of satisfaction with respect to completion time of Ji. For the bi-criteria scheduling problem, an 0 （ n^3 ） algorithm is proposed for finding nondominated solutions.  相似文献   

9.
As a basic mathematical structure,the system of inequalities over symmetric cones and its solution can provide an effective method for solving the startup problem of interior point method which is used to solve many optimization problems.In this paper,a non-interior continuation algorithm is proposed for solving the system of inequalities under the order induced by a symmetric cone.It is shown that the proposed algorithm is globally convergent and well-defined.Moreover,it can start from any point and only needs to solve one system of linear equations at most at each iteration.Under suitable assumptions,global linear and local quadratic convergence is established with Euclidean Jordan algebras.Numerical results indicate that the algorithm is efficient.The systems of random linear inequalities were tested over the second-order cones with sizes of 10,100,,1 000 respectively and the problems of each size were generated randomly for 10 times.The average iterative numbers show that the proposed algorithm can generate a solution at one step for solving the given linear class of problems with random initializations.It seems possible that the continuation algorithm can solve larger scale systems of linear inequalities over the secondorder cones quickly.Moreover,a system of nonlinear inequalities was also tested over Cartesian product of two simple second-order cones,and numerical results indicate that the proposed algorithm can deal with the nonlinear cases.  相似文献   

10.
A two-stage method is developed to solve a new class of multi-storage tank multi-source （MTMS） systems. In the first stage, the optimal storage policy of each tank is determined according to the electricity tariff, and the ground-level storage tank is modeled as a node. In the second stage, the genetic algorithm, combined with a repairing scheme, is applied to solve the pump scheduling problem. The objective of the pump scheduling problem is to ensure that the required volume is adequately provided by the pumps while minimizing the operation cost （energy cost and treatment cost）. The decision variables are the settings of the pumps and speed ratio of variable-speed pumps at time steps of the total operational time horizon. A mixed coding methodology is developed according to the characteristics of the decision variables. Daily operation cost savings of approximately 11% are obtained by application of the proposed method to a pressure zone of S. Y. water distribution system （WDS）, China.  相似文献   

11.
Suppose {X, X n ;n≥1} is a sequence i.i.d.r.v. withEX=0 andEX 2<∞. Shao (1995) proved a conjecture of Révész (1990); ifP(X=±1)=1/2, then
. Furthermore he conjectured that
. In this paper we prove that if then this conjecture is ture. Project (10071072) supported by National Natural Science Foundation of China(NSFC).  相似文献   

12.
Let Γd2nbe the set of trees with a given diameter d having a perfect matching,where 2n is the number of vertex.For a tree T in Γd2n,let Pd+1be a diameter of T and q = d m,where m is the number of the edges of perfect matching inPd+1.It can be found that the trees with minimal energy in Γd2nfor four cases q = d 2,d 3,d 4,[d2],and two remarks aregiven about the trees with minimal energy in Γd2nfor2d 33q d 5 and [d2] + 1 q2d 33 1.  相似文献   

13.
In this work, we made progress on the problem that lr(○×)lp(○×)lq is a Banach algebra under schur product. Our results extend Tonge's results. We also obtained estimates for the norm of the random quadralinear form A:lMr×lNp×lKq×lHs→ C, defined by: A(ei, ej, ek, es)=aijks, where the (aijks)'s are uniformly bounded, independent, mean zero random variables. We proved that under some conditions lr(○×)lp(○×)lq (○×)ls is not a Banach algebra under schur product.  相似文献   

14.
The sequences {Zi,n, l≤i≤n}, n≥l have multi-nomial distribution among i.i.d. random variables {X1,i, i≥1}, {X2,i,u≥l }, …, {Xm,i, i≥1 }. The extreme value distribution Gz(x) of this particular triangular array of i.i.d, random variables Z1,n, Z2Zn,n is discussed in this paper. We found a new type of not max-stable extreme value distributions, i) Gz(x) = r-1∏i=1ФAiαi(x) × Фαr (x);ii) Gz (x) = r-1∏i=1ψAiαi (x) × ψαr (x); iii) Gz (x) = r-1∏i=1 ∧Ai (λix) × A(x), r≥2, 0＜α1≤α2≤…≤αr and λi∈ (0,1] for i, l≤i≤r-1 which occur if Fj, …, Fm belong to the same MDA.  相似文献   

15.
A hybrid two-stage flowshop scheduling problem was considered which involves m identical parallel machines at Stage 1 and a burn-in processor M at Stage 2, and the makespan was taken as the minimization objective. This scheduling problem is NP-hard in general. We divide it into eight subcases. Except for the following two subcases： （1） b≥ an, max{m, B} 〈 n; （2） a1 ≤ b ≤ an, m ≤ B 〈 n, for all other subcases, their NP-hardness was proved or pointed out, corresponding approximation algorithms were conducted and their worst-case performances were estimated. In all these approximation algorithms, the Multifit and PTAS algorithms were respectively used, as the jobs were scheduled in m identical parallel machines.  相似文献   

16.
The dilaton in Weyl-Scale induced gravitational theory is regarded as a candidate of dark energy. When the potential of dilaton field is taken as the form Wσ ＋ σ^2e^-βσ2, that there exist attractor solutions to the canonical dilatonic dark energy model and the phontam model, and these attractors correspond to an equation of state ω = -1 and a cosmic density parameter Ωσ = 1, which are important features for a dark energy model and can fit with the current observations. We find a sufficient condition of the existence of a late time de Sitter attractor. The attractor behaviors, the evolutions of the state parameter ω and the cosmic density parameter Ω, the evolution of X （σ/σ0） and Y （σ/σ0^2） with respect to N（ln a）are shown numerically.  相似文献   

17.
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problemP2|decr|l p (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of thel p norm of every machine's load. It is shown thatLS algorithm is optimal for anyl p norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problemsP2|online|l p andP2|decr|l p are presented. Project supported by the National Natural Science Foundation of China (Nos. 10271110, 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China  相似文献   

18.
The purpose of this research is to analyze the relationship between individual, institutional and demographic characteristics on one hand and the research productivity of agriculture faculty members on the other. The statistical population of the research comprises 280 academic staff in agricultural faculties all over Tehran Province. The data regarding research productivity and demographic characteristics were extracted from the faculty members’ profiles. Questionnaires were utilized to collect information concerning individual and institutional variables. The reliably of the questionnaire was calculated to be between 0.74 and 0.97 using the Cronbach’s Alpha. The regression analysis revealed that from among demographic characteristics two variables, namely, academic rank and age ( \textR\textAD 2 {\text{R}}_{\text{AD}}^{ 2}  = 0.265), among individual characteristics, three variables, namely, working habits, creativity as well as autonomy and commitment ( \textR\textAD 2 {\text{R}}_{\text{AD}}^{ 2}  = 0.097), and among institutional characteristics four variables namely, network of communication with colleagues, resources of facilities, corporate management and clear research objectives ( \textR\textAD 2 {\text{R}}_{\text{AD}}^{ 2}  = 0.151) were significant predictors for agricultural faculty members’ research productivity.  相似文献   

19.
Suppose {Xi,i≥1} and {Yi, i≥1} are two independent sequences with distribution functions and , respectively. Zi,n is the combination of Xi and Yi with a probability for each I with 1≤ i≤n. The extreme value distribution GZ(x) of this particular triangular array of the i.i.d. Random variables Z1,n,… Z2,n, Zn,n is discussed. We found a new form of the extreme value distributions i)ΦAα1(x)Φα2 and ii) ψAα(x)ψα2(x)α1<α2), which are not max-stable. It occurs if FX and FY belong to the same MDA(Φ) or MDA(Ψ).  相似文献   

20.
We derive necessary and sufficient conditions for the existence and an expression of the （anti）reflexive solution with respect to the nontrivial generalized reflection matrix P to the system of complex matrix equations AX = B and XC = D. The explicit solutions of the approximation problem min x∈Ф ｜｜X - E｜｜F was given, where E is a given complex matrix and Ф is the set of all reflexive （or antireflexive） solutions of the system mentioned above, and ｜｜·｜｜ is the Frobenius norm. Furthermore, it was pointed that some results in a recent paper are special cases of this paper.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号