A new heuristic for resource-constrained project scheduling in stochastic networks using critical chain concept

This paper presents a newly developed resource-constrained project scheduling method in stochastic networks by merging the new and traditional resource management methods. In each project, the activities consume various types of resources with fixed capacities. The duration of each activity is a random variable with a given density function. Since the backward pass method is implemented for feeding-in resources. The problem is to determine the finish time of each activity instead of its start time. The objective of the presented model is defined as minimizing the multiplication of expected project duration and its variance. The values of activities finish times are determined at decision points when at least one activity is ready to be operated and there are available resources. If at a certain point of time, more than one activity is ready to be operated but available resources are lacking, a competition among ready activities is carried out in order to select the activities which must be operated first. This paper suggests a competition routine by implementing a policy to maximize the total contribution of selected activities in reducing the expected project duration and its variance. In this respect, a heuristic algorithm is developed and compared with the other existing methods.     

机器带准备时间的三台平行机排序问题的线性时间算法

对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数),并证明了当ε=1/5时,对偶阈值算法DA3(1/5)的近似比为6/5,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法.     

A Tabu-Search Hyperheuristic for Timetabling and Rostering

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.     

Real time task scheduling allowing fuzzy due dates

The paper deals with periodical task scheduling. The tasks are described by fuzzy due dates and fuzzy execution times. The goal of scheduling is to find an optimal assignment of priorities such that the satisfaction associated with due dates and execution times be minimized. The paper shows how the rules associated with task priorities improve the optimal assignment search.     

具有通用机的n组工件的排序问题

本文讨论了具有n台速度相同的专用机,一台同速度的通用机的n组工件的Cmax问题,提出了改进的LPT算法,得到了近似算法的一个估计．     

A market-based multi-agent system model for decentralized multi-project scheduling

We consider a multi-project scheduling problem, where each project is composed of a set of activities, with precedence relations, requiring specific amounts of local and shared (among projects) resources. The aim is to complete all the project activities, satisfying precedence and resource constraints, and minimizing each project schedule length. The decision making process is supposed to be decentralized, with as many local decision makers as the projects. A multi-agent system model, and an iterative combinatorial auction mechanism for the agent coordination are proposed. We provide a dynamic programming formulation for the combinatorial auction problem, and heuristic algorithms for both the combinatorial auction and the bidding process. An experimental analysis on the whole multi-agent system model is discussed.     

Job selection and sequencing on a single machine in a random environment

We examine a single machine scheduling problem with random processing times and deadline. Given a set of independent jobs having specified initiation costs and terminal revenues, the objective is to select a subset of the jobs and sequence the selected jobs such that the expected profit is maximized. The job selection aspect considered by us marks a clear departure from the pure sequencing focus found in the traditional scheduling literature. In this paper, we assume an exponentially distributed deadline and do not allow preemption. Even under these conditions, the selection and sequencing problem remains quite difficult (unlike its pure sequencing counterpart); we in fact conjecture that the problem is NP-hard. However, we show that the problem can be efficiently solved as long as the cost parameter is agreeable or an approximate solution is acceptable. To this end, we describe several solution properties, present dynamic programming algorithms (one of which exhibits a pseudo-polynomial time worst-case complexity), and propose a fully-polynomial time approximation scheme. In addition, we study a number of special cases which can be solved in polynomial time. Finally, we summarize our work and discuss an extension where the jobs are precedence related.     

具有特殊工件的平行机在线排序问题

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686.     

GRASP and path relinking for project scheduling under partially renewable resources

Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this paper, we develop some preprocessing techniques and several heuristic algorithms for the problem. Preprocessing significantly reduces the dimension of the problems, therefore improving the efficiency of solution procedures. Heuristic algorithms based on GRASP and Path relinking are then developed and tested on existing test instances, obtaining excellent results.     

Supply chain scheduling: Just-in-time environment

We study the benefits of coordinated decision making in a supply chain consisting of a manufacturer, a distributor, and several retailers. The distributor bundles finished goods produced by the manufacturer and delivers them to the retailers to meet their demands. The distributor is responsible for managing finished goods inventory. An optimal production schedule of the manufacturer, if imposed on the distributor, may result in an increased inventory holding cost for the distributor. On the other hand, an optimal distribution schedule of the distributor, if imposed on the manufacturer, may result in an increased production cost for the manufacturer. In this paper we develop mathematical models for individual optimization goals of the two partners and compare the results of these models with the results obtained for a joint optimization model at the system level. We investigate the computational complexities of these scheduling problems. The experimental results indicate that substantial cost savings can be achieved at the system level by joint optimization. We also study conflict and cooperation issues in the supply chain. The cost of conflict of a supply chain partner is a measure of the amount by which the unconstrained optimal cost increases when a decision is to be made under the scheduling constraint imposed by the other partner. We quantify these conflicts and show that the cost of conflicts are significant. We also show that a cooperative decision will generate a positive surplus in the system which can be shared by the two partners to make cooperation and coordination strategy more attractive.