Scheduling multiple divisible loads in homogeneous star systems

In this paper we analyze scheduling multiple divisible loads on a star-connected system of identical processors. It is shown that this problem is computationally hard. Some special cases appear to be particularly difficult, so it is not even known if they belong to the class NP. Exponential algorithms and special cases solvable in polynomial time are presented. M. Drozdowski’s research partially supported by Polish Ministry of Science and Higher Education.     

A tight lower bound for job scheduling with cancellation

The Job Scheduling with Cancellation problem is a variation of classical scheduling problems in which jobs can be cancelled while waiting for execution. In this paper we prove a tight lower bound of 5 for the competitive ratio of any deterministic online algorithm for this problem, for the case where all jobs have the same processing time.     

Single machine batch scheduling problem with family setup times and release dates to minimize makespan

In this paper we consider the single machine batch scheduling problem with family setup times and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an time dynamic programming algorithm and an time dynamic programming algorithm for the problem, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the setup times of all the families and the processing times of all the jobs. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme (PTAS) for the problem.     

Online scheduling with rejection and withdrawal

We study an online scheduling problem with rejection, in which some rearrangement of the solution is allowed. This problem is called scheduling with rejection and withdrawal. Each arriving job has a processing time and a rejection cost associated with it, and it needs to be either assigned to a machine or rejected upon arrival. At termination, it is possible to choose at most a fixed number of scheduled jobs and withdraw them (i.e., decide to reject them). We study the minimization version, where the goal is to minimize the sum of the makespan and the total rejection cost (which corresponds to the penalty), and the maximization problem, where the goal is to maximize the sum of the minimum load and the total rejection cost (which corresponds to profit). We study environments of machines, which are the case of m identical machines and the case of two uniformly related machines, and show a strong relation between these problems and the related classic online scheduling problems which they generalize, in contrast to standard scheduling with rejection, which typically makes the scheduling problems harder.     

Performance bound analysis of a heuristic for the total weighted flowtime problem with fixed delivery dates

We consider single-machine scheduling with fixed delivery dates, which are given or determined before the jobs are processed. A job is delivered on the earliest fixed delivery date that is no earlier than its completion time. The flowtime of a job is defined as its delivery date. The objective is to minimize the total weighted flowtime of the jobs. The largest ratio first (LRF) rule is a heuristic that sequences jobs in nonincreasing order of w_j/p_j, where p_j and w_j are the processing time and weight of job J_j, respectively. We investigate the performance bounds of the LRF heuristic under different scenarios of the problem. We conducted computational experiments to test the performance of the heuristic. The results show that the LRF heuristic is able to produce near-optimal and optimal solutions.     

Design and performance evaluation of a fuzzy based traffic conditioner for differentiated services

The current Internet can only provide the best-effort services. By growing the Internet and its applications, new services with different requirements are developed. The differentiated services (Diffserv) [S. Blake, M. Carlson, E. Davies, Z. Wang, W. Weiss, An Architecture for Differentiated Services, IETF RFC 2475, 1998; K. Nichols, V. Jacobson, L. Zhang, A Two-bit Differentiated Services Architecture for the Internet, IETF RFC 2638, July 1999; T. Li, Y. Rekhter, A Provider Architecture for Differentiated Services and Traffic Engineering (PASTE), IETF RFC 2430, October 1998] is a scalable model for providing end-to-end quality of services. A Diffserv router consists of different components including classifier, meter, marker, dropper, shaper and scheduler. In this paper, we use the benefits of the fuzzy logic controller to design a fuzzy based traffic conditioner for Internet differentiated services. Our proposed model consists of three major parts: a fuzzy meter/marker (FM), a fuzzy active queue management (FAQM) algorithm and a fuzzy scheduler (FS). The proposed FM used to measure and mark the input traffic is based on the single rate three colors meter (srTCM) mechanism [J. Heinane, et al., A Single Rate Three Color Marker, RFC 2697, September 1999]. The FM meters an IP packet stream and marks its packets GREEN, YELLOW, or RED. The proposed FAQM is a fuzzy implementation of the well-known BLUE active queue management (AQM) algorithm [W. Feng, D. Kandlur, D. Saha, K. Shin, BLUE: A New Class of Active Queue Management Algorithms U. Michigan CSE-TR-387-99, April 1999]. To achieve a good throughput and reasonable packet loss ratio, the proposed FAQM mechanism employs a fuzzy logic controller. The third part of the proposed fuzzy traffic conditioner is FS. It is based on the traditional weighted fair queue (WFQ) mechanism [A. Demers, S. Keshav, S. Shenker, Analysis and simulation of a fair queueing algorithm, in: SIGCOMM Symposium on Communications Architectures and Protocols, Austin, Texas, September 1989, pp. 1–12] that tunes the weight of each queue by a fuzzy logic controller. To evaluate the performance of the proposed model, we developed a software in C++ environment to simulate it. Different network topologies with different traffic parameters were performed. The simulation results easily helped us to judge the merit of the proposed FM, FAQM and FS because of their remarkable performance over the traditional non-fuzzy mechanisms.     

Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time

We consider online scheduling on m unbounded parallel-batch machines to minimize maximum flow-time of the jobs. We show that no online algorithm can have a competitive ratio less than 1+αm, where αm is the positive root of α²+(m+1)α−1=0, and this lower bound is still valid even when all jobs have the same processing times. Then we provide an online algorithm of competitive ratio 1+1/m. When the jobs have the same processing times, we present a best possible online algorithm of competitive ratio 1+αm.     

按订单生产的高级计划与排程系统研究

分析离散型按订单生产的中小企业生产过程,建立生产计划系统模型,采用模拟退火算法设计了基于订单的生产计划和排程系统.     

蚁群算法在生产调度中的应用

介绍了蚁群算法的基本思想,以旅行商问题说明了蚁群算法的模型结构,总结了蚁群算法在作业车间以及流水车间中的应用,并与其它启发式算法进行了简单的比较。在分析了目前半导体生产线调度研究现状的基础上,探讨了蚁群算法在半导体生产线调度中的应用前景。