A note on resource allocation scheduling with group technology and learning effects on a single machine

In this article, single-machine group scheduling with learning effects and convex resource allocation is studied. The goal is to find the optimal job schedule, the optimal group schedule, and resource allocations of jobs and groups. For the problem of minimizing the makespan subject to limited resource availability, it is proved that the problem can be solved in polynomial time under the condition that the setup times of groups are independent. For the general setup times of groups, a heuristic algorithm and a branch-and-bound algorithm are proposed, respectively. Computational experiments show that the performance of the heuristic algorithm is fairly accurate in obtaining near-optimal solutions.     

面向混合负载的集群资源弹性调度

针对目前集群资源调度方法难以适应互联网业务多样化、定制化特征的问题,提出了一种面向混合负载的集群资源弹性调度方法.该方法通过构建作业约束描述语言,允许作业基于自身负载特征提出多维度的资源申请和具有负载意识的资源调度算法,实现在同一集群内各类业务统一部署与管理,及时匹配资源需求的变化;通过建立作业的软约束与硬约束之间的转化机制,满足作业在不同执行阶段对资源的定制化需求.实验表明,该方法相比于Hadoop,可允许作业利用较少资源获得更优性能,在实际生产系统中,基于该方法可将集群资源利用率由62％提升到75％.     

Single-machine due-window assignment scheduling based on common flow allowance,learning effect and resource allocation

This article considers a single-machine due-window assignment scheduling problem based on a common flow allowance (i.e. all jobs have slack due window (SLKW)). We assume that the actual processing time of a job is a function of its position in a sequence (learning effect) and its continuously divisible and non-renewable resource allocation. The problem is to determine the optimal due windows, the optimal resource allocation and the processing sequence simultaneously to minimise costs for earliness, tardiness, the window location, window size, makespan and resource consumption. For a linear or a convex function of the amount of a resource allocated to the job, we provide a polynomial time algorithm, respectively. Some extensions of the problem are also shown.     

Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity

In this paper, we consider common due-window assignment and scheduling problems with general position-dependent processing times involving deteriorating and compressible maintenance activity on a single machine. Two models associated with maintenance activity are examined in this article, in which the maintenance length is assumed to be either time-dependent and compressible or position-dependent and compressible. The objective is to find jointly the location and size of due-window, position of maintenance as well as resource amount allocated to it, and job sequence to minimise a total cost function based on earliness, tardiness, window location, window size and resource cost. We show that the problem considered in each of the two models’ setting can be optimally solved with polynomial time algorithm by reducing to assignment problem. Finally, two examples are provided to illustrate the solution procedures.     

The integration of resource allocation and time buffering for bi-objective robust project scheduling

In the recent decades, the recognition that uncertainty lies at the heart of modern project management has induced considerable research efforts on robust project scheduling for dealing with uncertainty in a scheduling environment. The literature generally provides two main strategies for the development of a robust predictive project schedule, namely robust resource allocation and time buffering. Yet, the previous studies seem to have neglected the potential benefits of an integration between the two. Besides, few efforts have been made to protect simultaneously the project due date and the activity start times against disruptions during execution, which is desperately demanded in practice. In this paper, we aim at constructing a proactive schedule that is not only short in time but also less vulnerable to disruptions. Firstly, a bi-objective optimisation model with a proper normalisation of the two components is proposed in the presence of activity duration variability. Then a two-stage heuristic algorithm is developed which deals with a robust resource allocation problem in the first stage and optimally determines the position and the size of time buffers using a simulated annealing algorithm in the second stage. Finally, an extensive computational experiment on the PSPLIB network instances demonstrates the superiority of the combination between resource allocation and time buffering as well as the effectiveness of the proposed two-stage algorithm for generating proactive project schedules with composite robustness.     

Single machine due-window assignment scheduling with resource-dependent processing times to minimise total resource consumption cost

This paper considers a single-machine scheduling problem involving convex resource-dependent processing times and due-window assignment simultaneously. The goal is to minimise the total resource consumption cost under the constraint that the schedule cost involving earliness, tardiness, window location, window size and makespan does not exceed a given limit for two popular due window assignment methods: the common flow allowance (slack) due window assignment method (referred to SLKW) and the common due window assignment method (referred to CONW). We show that the problem can be solved in polynomial time. Some extensions of the problem are also given.     

A note on single machine scheduling and due date assignment with general position-dependent processing times

This note considers single machine scheduling and due date assignment in which a job’s processing time depends on its position in a sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and the total earliness of the scheduled jobs. We analyse these problems with three different due date assignment methods. We provide a generic polynomial-time dynamic programming algorithm to solve the problems.     

Due-date assignment scheduling involving job-dependent learning effects and convex resource allocation

ABSTRACT

This article addresses single machine resource allocation scheduling problems with learning effects, where learning effects mean job-dependent position-based learning effects. For the common due-date assignment (CON) and slack due-date assignment (SLK) methods, a bi-cost analysis of the scheduling cost and the total weighted resource consumption cost is provided. The objective is to determine the optimal job sequence and the resource allocation simultaneously, such that the scheduling cost (the total weighted resource consumption cost) is minimized subject to the total weighted resource consumption cost (the scheduling cost) being limited. Solution procedures are provided for the problems under consideration.     

Ant colonies with cooperative process applied to the resource allocation problem

Abstract

In this paper, a novel algorithm describing ant colonies, with cooperation, is proposed to solve the resource allocation problem. The resource allocation problem is to allocate resources to activities, with the objective of optimizing the cost function. In our study, we viewed the search in ant colonies as a mechanism providing a main portion of diversity in search space. The cooperative process conducts fine‐tuning for the solution provided by ant colonies, and it has the ability to escape from poor local optima. In this paper, several examples are tested to prove the superiority of our proposed algorithm. From simulation results, the proposed algorithm indeed has remarkable performance.     

Flexible job-shop scheduling problem with resource recovery constraints

In this work, we introduce a Flexible Job-shop Scheduling Problem with Resource Recovery Constraints (FRRC). In the FRRC, besides the constraints of the classical Flexible Job-shop Scheduling Problem (FJSP), operations may require resources to be processed. The resources are available in batches and a recovery time is required between each batch. This problem is inspired by a real situation faced by a brewing company where different yeasts are available in a limited quantity and are recovered only once they have been completely used. The objective is to schedule the operations such that the makespan is minimised. A mathematical model and a metaheuristic based on a General Variable Neighborhood Search is proposed for the solution of the FRRC. Computational results over a large set of instances, adapted from the FJSP literature, are presented.     

A GRASP algorithm for flexible job-shop scheduling problem with limited resource constraints

A greedy randomised adaptive search procedure (GRASP) is an iterative multi-start metaheuristic for difficult combinatorial optimisation. The GRASP iteration consists of two phases: a construction phase, in which a feasible solution is found and a local search phase, in which a local optimum in the neighbourhood of the constructed solution is sought. In this paper, a GRASP algorithm is presented to solve the flexible job-shop scheduling problem (FJSSP) with limited resource constraints. The main constraint of this scheduling problem is that each operation of a job must follow an appointed process order and each operation must be processed on an appointed machine. These constraints are used to balance between the resource limitation and machine flexibility. The model objectives are the minimisation of makespan, maximum workload and total workload. Representative benchmark problems are solved in order to test the effectiveness and efficiency of the GRASP algorithm. The computational result shows that the proposed algorithm produced better results than other authors’ algorithms.     

No-wait two-machine permutation flow shop scheduling problem with learning effect,common due date and controllable job processing times

We consider a two-machine no-wait permutation flow shop common due date assignment scheduling problem where the processing time of a job is given as a function of its position in the sequence and its amount of resource allocated to this job. The common due date (CON) assignment method means that all the jobs are given a common due date. We need to make a decision on the common due date, resource allocation and the sequence of jobs to minimise total earliness, tardiness, common due date cost and total resource cost. We show that the problem remains polynomially solvable under the proposed model.     

基于产业链演化的物流网络资源配置策略

从基础设施、信息系统、服务功能等角度分析物流网络资源,总结地理环境和商业市场因素对物流基础设施的空间构型的影响,提出从市场角度研究物流资源配置的必要性.分析社会经济系统中经济运行链式结构由企业集群至产业链的发展趋势,从服务范围、服务核心、需求市场、利用效率等层面研究不同经济运行结构条件对物流网络资源影响,从设施、信息和功能等分项角度总结瓶颈问题,提出资源配置对策.     

A manufacturing resource allocation method with knowledge-based fuzzy comprehensive evaluation for aircraft structural parts

Manufacturing of aircraft structural parts has the characteristics of multiple varieties, complex structures and small batches, which make the manufacturing resource allocation highly difficult. This paper proposes a manufacturing resource allocation method with knowledge-based fuzzy comprehensive evaluation, considering multiple manufacturing resources including process planners, machine tools and cutting tools, as well as manufacturing process schemes of aircraft structural parts. Knowledge in terms of experts’ experience and historical data is used for fuzzy comprehensive evaluation. A manufacturing resource allocation model is proposed based on the analysis of manufacturing processes of aircraft structural parts. The capability of planners, the complexity of structural parts, the reliability of machine tools, the reliability of cutting tools and the correlations between manufacturing resources and structural parts are evaluated using the fuzzy comprehensive evaluation method. Multiple manufacturing resources are allocated based on the fuzzy comprehensive evaluation results. A prototype system has been implemented and a case study is used to validate the proposed approach.     

A hybrid nested partitions algorithm for scheduling flexible resource in flow shop problem

Production scheduling with flexible resources is critical and challenging in many modern manufacturing firms. This paper applies the nested partitions (NP) framework to solve the flexible resource flow shop scheduling (FRFS) problem using an efficient hybrid NP algorithm. By considering the domain knowledge, the ordinal optimisation principle and the NEH heuristics are integrated into the partitioning scheme to search the feasible region. An efficient resource-allocation procedure is built into the sampling scheme for the FRFS problem. A large number of benchmark examples with flexible resources are tested. The test results show that the hybrid NP algorithm is more efficient than either generic NP or heuristics alone. The algorithm developed in this study is capable of selecting the most promising region for a manufacturing system with a high degree of accuracy. The algorithm is efficient and scalable for large-scale problems.     

Synchronization of yard truck scheduling and storage allocation in container terminals

Yard truck scheduling and storage allocation, as two separate subproblems in port operations, have been extensively studied in the past decades. However, from the operational point of view, they are highly interdependent. This article proposes an integer programming model in which yard truck scheduling and storage allocation problems are formulated as a whole for heterogeneous import containers. Different stacking times at yard blocks is modelled as well. The objective of the proposed model is to reduce the congestion and waiting time of yard trucks in the terminal so as to decrease the makespan of discharging containers. Owing to the inherent computational complexity, a genetic algorithm and a greedy heuristic algorithm have been designed. Computational experiments show that the proposed genetic algorithm and greedy algorithm are both effective in solving the studied problem.