共查询到16条相似文献，搜索用时 203 毫秒
1.
HAN Shu-guang JIANG Yi-wei HU Jue-liang 《浙江大学学报(A卷英文版)》2007,8(1):127-133
INTRODUCTION In this paper we investigate the uniform ma-chines scheduling problem with machine activationcost. This problem has application in garment pro-duction of international trade and is motivated by thefollowing scenario. Import-export company is com-pared to scheduler in this model, and orders are jobs,which arrive one by one. And garment factories canbe regarded as machines. Since jobs should be fin-ished on time, scheduler will choose a reasonablenumber of machines to make the… 相似文献
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.
Ehsan Ullah Munir Jian-zhong Li Sheng-fei Shi Zhao-nian Zou Qaisar Rasool 《浙江大学学报(A卷英文版)》2008,9(12):1715-1723
Heterogeneous computing （HC） environment utilizes diverse resources with different computational capabilities to solve computing-intensive applications having diverse computational requirements and constraints. The task assignment problem in HC environment can be formally defined as for a given set of tasks and machines, assigning tasks to machines to achieve the minimum makespan. In this paper we propose a new task scheduling heuristic, high standard deviation first （HSTDF）, which considers the standard deviation of the expected execution time of a task as a selection criterion. Standard deviation of the expected execution time of a task represents the amount of variation in task execution time on different machines. Our conclusion is that tasks having high standard deviation must be assigned first for scheduling. A large number of experiments were carried out to check the effectiveness of the proposed heuristic in different scenarios, and the comparison with the existing heuristics （Max-min, Sufferage, Segmented Min-average, Segmented Min-min, and Segmented Max-min） clearly reveals that the proposed heuristic outperforms all existing heuristics in terms of average makespan. 相似文献
4.
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%. 相似文献
5.
Optimal online algorithms for scheduling on two identical machines under a grade of service 总被引：8，自引：0，他引：8
INTRODUCTIONWe study the problem of online scheduling on two identical parallel machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. The goal is to minimize the makespan under the constraint that all requests are satisfied. This problem was first proposed by Hwang et al.(2004) and is motivated by the following scenario. In the service industry, the service providers often have special customers, such as, go… 相似文献
6.
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. 相似文献
7.
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＂. 相似文献
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.
10.
Semi On-line Scheduling Problem for Maximizing the Minimum Machine Completion Time on m Identical Machines 总被引：2，自引：0，他引：2
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. 相似文献
11.
考虑了两台同类机极小化总完工时间的分批排序问题,给出了计算复杂性为O(n3)的动态规划算法,并将此算法推广到了工件具有学习效应的情况. 相似文献
12.
13.
Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines 总被引：1，自引：0，他引：1
INTRODUCTION Sequencing and scheduling are forms of deci-sion-making which play a crucial role in most manufacturing and production systems as well as in most information-processing environments, and also exist in transportation and distribution settings and in other types of service industries. A scheduling problem is called on-line if it re-quires scheduling jobs irrevocably on the machines as soon as they are given, without any knowledge about jobs that follow later on. If we have full… 相似文献
14.
基于启发式算法的工作流调度算法目标单一,无法保证用户满意度,且多目标调度算法少、性能差。为了改善现状,提出基于多阶段PSO的多目标工作流调度算法MSPSO,分析工作流任务的层次结构,按层次进行多阶段PSO调度,结合排队理论估算每阶段调度需要的虚拟机数量,控制PSO搜索空间,使算法能快速找到最优解。用4种真实科学工作流在CloudSim环境下进行仿真实验。结果表明,MSPSO算法资源利用率提高了1.81%,能耗降低了9.16%,任务违约率低至0.075%。MSPSO调度算法不仅能动态增减虚拟机,降低能耗,还能在保证截止时间的前提下降低任务违约率,提高资源利用率。 相似文献
15.
为了研究更具实际意义的带有位置依赖影响的分组调度决策问题,建立了一般性位置依赖的分组调度模型.在模型中,分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式,且没有要求限制其函数单调性.通过数理逻辑分析和证明,把所研究的问题模型分解为组调度过程和工件调度过程,并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题,进而分析问题求解的计算复杂度.研究表明,即使在一般性位置依赖的模型假设下,单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的. 相似文献
16.
The permutation flow shop scheduling problems with deteriorating jobs and rejection on dominant machines were studied. The objectives are to minimize the makespan of scheduled jobs plus the total rejection penalty and the total completion time of scheduled jobs plus the total rejection penalty. For each objective, polynomial time algorithms based on dynamic programming were presented. 相似文献