Single-machine group scheduling with processing times dependent on position,starting time and allotted resource

This article considers scheduling problems on a single machine with learning effect, deteriorating jobs and resource allocation under group technology (GT) assumption. We assume that the actual processing time of a job depends on the job position, the group position, the starting time and the amount of resource allocated to them concurrently, and the actual setup times of groups depend on the group position and the amount of resource allocated to them concurrently. Two resource allocation functions are examined for minimizing the weighted sum of makespan and total resource cost. We prove that the problems have polynomial solutions under the condition that the number of jobs in each group are the same.     

具有恶化效应和凸资源分配关系的单机排序问题

研究工件加工时间具有恶化效应和凸资源关系的单机排序问题,其中工件的实际加工时间是其正常的加工时间,工件开工时间(具有恶化效应)及消耗资源量的函数。目标为在最大完工时间(总完工时间、总等待时间、完工时间总绝对差与等待时间总绝对差)小于或等于给定常数的条件下找到工件的最优排序和最优的资源分配使工件的总资源消耗量最少。在单机状态下,证明了此问题是多项式时间可解的,并给出了求解该问题的算法和数值实例。     

带凸资源和恶化效应的单机松弛窗口排序

研究带凸资源和恶化效应的单机窗口指派排序问题,其中窗口指的是松弛窗口,凸资源和恶化效应指的是工件的实际加工时间是其开始加工时间的线性函数,是其资源消耗量的凸函数。目标是确定工件的加工顺序,资源分配量以及窗口的开始加工时间和长度使其在总资源消耗费用(与窗口有关的排序费用)有上界限制的条件下,极小化与窗口有关的排序费用(总资源消耗费用)。获得了求解上述问题的最优算法,证明了该问题是多项式时间可解的。     

Approximation algorithms for scheduling on multi-core processor with shared speedup resources

We consider a joint resource partition and scheduling problem. We are given $m$ identical cores and discrete resources of total size $k$. We need to partition the resources among these cores. A set of jobs must be processed non-preemptively on these cores after the resource partition. The processing time of a job on a core depends on the size of resources allocated to that corresponding core. The resource allocation scheme is static, i.e., we cannot change the amount of resources that was allocated to a core during the whole scheduling. Hassidim et al. (2013) investigated this problem with a general processing time function, i.e., the processing time of a job is an arbitrary function of the level of resources allocated to that core. They provided an algorithm with approximation ratio of 36. In this paper, we improve the approximation ratio to 8 by presenting a new resource partition scheme. Next, we consider a special model where the core’s speed is proportional to its allocated resource, then we present two algorithms with improved approximation ratios.     

Unrelated parallel machines scheduling with deteriorating jobs and resource dependent processing times

We consider unrelated parallel machines scheduling problems involving resource dependent (controllable) processing times and deteriorating jobs simultaneously, i.e., the actual processing time of a job is a function of its starting time and its resource allocation. Two generally resource consumption functions, the linear and convex resource, were investigated. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. This paper focus on the objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. If the number of unrelated parallel machines is a given constant, we show that the problems remain polynomially solvable under the proposed model.     

Single-machine scheduling with convex resource dependent processing times and deteriorating jobs

In this study, we consider scheduling problems with convex resource dependent processing times and deteriorating jobs, in which the processing time of a job is a function of its starting time and its convex resource allocation. The objective is to find the optimal sequence of jobs and the optimal convex resource allocation separately. This paper focus on the single-machine problems with objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. It shows that the problems remain polynomially solvable under the proposed model.     

Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time

In this paper, we consider single-machine due window assignment and scheduling with a common flow allowance and controllable job processing times, subject to unlimited or limited resource availability. Due window assignment with a common flow allowance means that each job has a job-dependent due window, the starting time and completion time of which are equal to its actual processing time plus the job-independent parameters q₁ and q₂, respectively, which are common to all the jobs. The processing time of each job is either a linear or a convex function of the amount of a common continuously divisible resource allocated to the job. We study five versions of the problem that differ in terms of the objective function and processing time function being used. We provide structural properties of the optimal schedules and polynomial-time solution algorithms for the considered problems.     

路政应急管理中资源布局的混合整数规划模型

本文根据道路灾害事故的发生特点,对城市路桥养护系统的运行模式和资源的合理调用机理进行分析,考虑到事发地点潜在的资源需求概率,建立资源布局的混合整数规划模型.本模型中资源布局方案的调度决策基础是在灾害事故的资源需求不发生变化的条件下,使得每个救助点的资源同时部分地为辖区内现有事故和潜在事故服务,而现有事故的剩余需求由其他救助点派出资源来满足.该模型的目标是解决城市中因同一时间段内发生两起灾害事故而造成路桥破坏导致的救助资源短缺问题,同时避免资源的闲置浪费.最后,通过算例证明,本方法较通常方法对城市总的资源配置量大大减少.     

Arrangement Increasing Resource Allocation

Consider a system composed of several units. The performance of each unit can be affected by providing a portion of a limited amount of costly resources available. An allocation of resources to a unit results in a unit’s response that depends on the level of resources allocated to it and some of its random parameters. In this paper we consider cases where each unit has one or two random parameters. The overall performance of the system is mapped by a function on the vector of responses generated by all the units in the system. Our interest is in identifying the conditions on the response function of the units, the system performance function and the random parameters under which the random system performance as a function of the resource allocation has stochastic arrangement increasing property. This allows one to substantially reduce the number of allocation that needs to be searched to identify an optimal allocation that maximizes the expected utility derived from the system response as a result of the resource allocation.     

Single machine group scheduling with time and position dependent processing times

In the paper two resource constrained single-machine group scheduling problems with time and position dependent processing times are considered. By time and position dependent processing times and group technology assumption, we mean that the processing time of a job is defined by the function of its starting time and position in the group, and the group setup times of a group is a positive strictly decreasing continuous function of the amount of consumed resource. We present polynomial solutions for the makespan minimization problem under the constraint that the total resource consumption does not exceed a given limit, and the total resource consumption minimization problem under the constraint that the makespan does not exceed a given limit, respectively.     

Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases

In many large-scale project scheduling problems, multiple projects are either taking place at the same time or scheduled into a tight sequence in order to efficiently share a common resource. One example of this is the computing resource allocation at an Application Service Provider (ASP) which provides data processing services for multiple paying customers. Typical services provided by ASPs are data mining, payroll processing, internet-based storage backup services and Customer Relation Management (CRM) services. The processing mode of an ASP can be either batch or concurrent, depending on the type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one customer request at a time in order to minimize the context switching overhead. While the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to process a service request depends on the computing resource allocated to that request. The related issue of achieving an optimal use of resources at ASPs leads to problem of project scheduling with controllable project duration.In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project duration and hard resource constraints. Two types of problems are considered. In type I, the duration of each project includes a constant and a term that is inversely proportional to the amount of resource allocated. In type II, the duration of each individual project is a continuous decreasing function of the amount of resource allocated.     

软件模块测试中的动态资源分配问题

为有效利用测度过程中投入的测试资源,提高测试效率,本文考虑将测试过程为多个阶段并为各个阶段动态分配测试资源的方法,为此提出两种动态分配测试资源模型,当测试资源总数一定时,测试约束时各软件模块中剩余错误平均数量小的模型;当给定测试约束时各软件模块中剩余错误平均数要达到的预定指标时,所用的测试资源最少的模型。     

Simultaneous Job Scheduling and Resource Allocation on Parallel Machines

Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time of a job is determined internally by the amount of the resources allocated. In these situations, both the cost associated with the job schedule and the cost of the resources allocated should be taken into account. Therefore, job scheduling and resource allocation should be carefully coordinated and optimized jointly in order to achieve an overall cost-effective schedule. In this paper, we study a parallel-machine scheduling model involving both job processing and resource allocation. The processing time of a job is non-increasing with the cost of the allocated resources. The objective is to minimize the total cost including the cost measured by a scheduling criterion and the cost of all allocated resources. We consider two particular problems of this model, one with the scheduling criterion being the total weighted completion time, and the other with that being the weighted number of tardy jobs. We develop a column generation based branch and bound method for finding optimal solutions for these NP-hard problems. The method first formulates the problems as set partitioning type formulations, and then solves the resulting formulations exactly by branch and bound. In the branch and bound, linear relaxations of the set partitioning type formulations are decomposed into master problems and single-machine subproblems and solved by a column generation approach. The algorithms developed based on this method are capable of solving the two problems with a medium size to optimality within a reasonable computational time.     

Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times

This paper addresses single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times. Due-window assignment with common flow allowances means that each job has a job-dependent due window, the start time and finish time of which are equal to its actual processing time plus individual job-independent parameters shared by all the jobs, respectively. The processing time of each job can be controlled by extra resource allocation as a linear function of the amount of a common continuously divisible resource allocated to the job. Two criteria are considered, where one criterion is an integrated cost consisting of job earliness, weighted number of tardy jobs, and due-window assignment cost, while the other criterion is the resource consumption cost. Four different models are considered for treating the two criteria. It is shown that the problem under the model where the two criteria are integrated into a single criterion is polynomially solvable, while the problems under the other three models are all NP-hard and an optimal solution procedure is developed for them. Two polynomially solvable cases are also identified and investigated. Finally, numerical studies with randomly generated instances are conducted to assess the performance of the proposed algorithms.     

Single-machine scheduling with time-and-resource-dependent processing times

We consider single-machine scheduling problems in which the processing time of a job is a function of its starting time and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We show that the problems remain polynomially solvable under the proposed model.     

Resource allocation for branch network system with considering heterogeneity based on DEA method

In this paper, we proposed a new DEA approach to allocate the resource in branch network system which is not covered by the existing resource allocation works under a centralized decision-making environment. The branch network system is typically appears in multi-national or multi-regional corporations, which has many branches across multiple locations. Given the spatial distribution of the production, we imposed additional restrictions on resource allocation and divided the resource inputs into three groups: fixed inputs, regional inputs that allocated to the branches in the same area and common resource that an additional resource allocated to all the branches. Then, we generalize the model further to accommodate technological heterogeneity due to the difference in the geographical locations of the branches. And the objective of the proposed models is to maximize the gross profits of the entire organization, which is a natural assumption for a for-profit organization. Finally, an example was presented to illustrate the proposed approach with heterogeneous technology is more practically feasible and superior than the prior approach with homogeneous technology.     

Scheduling jobs with time-resource tradeoff via nonlinear programming

We consider a scheduling problem where the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The objective is to find a resource allocation and a schedule that minimizes the makespan. We explicitly allow for succinctly encodable time-resource tradeoff functions, which calls for mathematical programming techniques other than those that have been used before. Utilizing a (nonlinear) integer mathematical program, we obtain the first polynomial time approximation algorithm for the scheduling problem, with performance bound (3+ε) for any ε>0. Our approach relies on a fully polynomial time approximation scheme to solve the nonlinear mathematical programming relaxation. We also derive lower bounds for the approximation.     

Optimal due-date assignment problem with learning effect and resource-dependent processing times

In this paper, we consider a single-machine earliness-tardiness scheduling problem with due-date assignment, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The due date assignment methods studied include the common due date, and the slack due date, which reflects equal waiting time allowance for the jobs. For each combination of due date assignment method and processing time function, we provide a polynomial-time algorithm to find the optimal job sequence, due date values, and resource allocations that minimize an integrated objective function, which includes earliness, tardiness, due date assignment, and total resource consumption costs.     

Multi-objectives Tabu Search based algorithm for progressive resource allocation

Military course of action planning involves time and space synchronization as well as resource and asset allocation. A mission could be seen as a defined set of logical ordered tasks with time and space constraints. The resources to task rules require that available assets should be allocated to each task. A combination of assets might be required to execute a given task. The couple (task, resources) constitutes an action. This problem is formulated as a multi-objectives scheduling and resource allocation problem. Any solution is assessed based on a number of conflicting and heterogeneous objectives. In fact, military planning officers should keep perfecting the plan based on the Commander’s criteria for success. The scheduling problem and resource allocation problem are considered as NP-Hard Problems [A. Guitouni, B. Urli, J.-M. Martel, Course of action planning: A project based modelling, Working Paper, Faculté des sciences de l’ administration, Université Laval, Québec, 2005]. This paper is concerned with the multi-objectives resource allocation problem. Our objective is to find adequate resource allocation for given courses of action schedule. To optimize this problem, this paper investigates non-exact solution methods, like meta-heuristic methods for finding potential efficient solutions. A progressive resource allocation methodology is proposed based on Tabu Search and multi-objectives concepts. This technique explores the search space so as to find a set of potential efficient solutions without aggregating the objectives into a single objective function. It is guided by the principle of maximizing the usage of any resource before considering a replacement resource. Thus, a given resource is allocated to the maximum number of tasks for a given courses of action schedule. A good allocation is a potential efficient solution. These solutions are retained by applying a combination of a dominance rule and a multi-criteria filtering method. The performance of the proposed Pareto-based approach is compared to two aggregation approaches: weighted-sum and the lexicographic techniques. The result shows that a Pareto-based approach is providing better solutions and allowing more flexibility to the decision-maker.     

Hybrid flowshop scheduling with machine and resource-dependent processing times

Most of research in production scheduling is concerned with the optimization of a single criterion. However the analysis of the performance of a schedule often involves more than one aspect and therefore requires a multi-objective treatment. In this research, with combination of two multiple objective decision-making methods, min–max and weighted techniques, a new solution presentation method and a robust hybrid metaheuristic, we solved sequence-dependent setup time hybrid flowshop scheduling problems. In this paper for reflecting real-world situation adequately, we assume the processing time of each job depends on the speed of machine and amount of resource allocated to each machine at the stage which is processed on it. In formulation of min–max type, the decision-maker can have the flexibility of mixed use of weights and distance parameter in expressing desired improvement on produced Pareto optimal solutions. To minimize makespan and total resource allocation costs, the proposed hybrid approach is robust, fast, and simply structured, and comprises two components: genetic algorithm and a variable neighborhood search. The comparison shows the proposal to be very efficient for different structure instances.