A two-stage heuristic for multi-activity and task assignment to work shifts

The multi-activity assignment problem consists of assigning interruptible activities to given work shifts so as to match as much as possible for each activity a demand curve in function of time. In this paper we consider an extension to this problem, called the multi-activity and task assignment problem, that additionally considers the assignment of uninterruptible pieces of work, called tasks. These possess properties such as worker qualifications, time windows for completion, fixed lengths and precedence relationships. We propose a mixed-integer programming formulation and a two-stage method to solve this problem. The first stage consists of an approximation mixed-integer programming model to assign tasks approximately taking into account the activities and the second involves a column generation heuristic for assigning activities and reassigning tasks at the same time. We suggest four different strategies for reassigning tasks. We conducted extensive computational tests on randomly generated instances in order to validate our method and to compare the various strategies. One strategy proved universally best when compared to the other three policies.     

Assigning multiple activities to work shifts

In some companies such as large retail stores, the employees perform different activities (e.g., cashier or clerk in a specific department) to respond to a customer demand for each activity that varies over the planning horizon and must be fulfilled as soon as possible. For a given time period, this demand translates into an ideal number of employees required for the corresponding activity. During a work shift, an employee can be assigned to several activities that are interruptible at any time and subject to operational constraints (required skills, minimum and maximum assignment durations). Given work shifts already assigned to the employees, the multi-activity assignment problem (MAAP) consists of assigning activities to the shifts such that the activity demands are satisfied as best as possible over the planning horizon. In this paper, we propose three integer programming models for the MAAP and develop various heuristics based on mathematical programming techniques. Computational results obtained on randomly generated MAAP instances show that a heuristic column generation method embedded into a rolling horizon procedure provides the best results in general.     

Optimal task assignment in homogeneous networks

This paper considers the problem of assigning the tasks of a distributed application to the processors of a distributed system such that the sum of execution and communication costs is minimized. Previous work has shown this problem to be tractable for a system of two processors or a linear array of N processors, and for distributed programs of serial parallel structures. Here we focus on the assignment problem on a homogeneous network, which is composed of N functionally-identical processors, each with its own memory. Some processors in the network may have unique resources, such as data files or certain peripheral devices. Certain tasks may have to use these unique resources; they are called attached tasks. The tasks of a distributed program should therefore be assigned so as to make use of specific resources located at certain processors in the network while minimizing the amount of interprocessor communication. The assignment problem in such a homogeneous network is known to be NP-hard even for N=3, thus making it intractable for a network with a medium to large number of processors. We therefore focus on task assignment in general array networks, such as linear arrays, meshes, hypercubes, and trees. We first develop a modeling technique that transforms the assignment problem in an array or tree into a minimum-cut maximum-flow problem. The assignment problem is then solved for a general array or tree network in polynomial time     

A two-phase mathematical-programming heuristic for flexible assignment of activities and tasks to work shifts

In the service industry, workers perform work shifts and are assigned to interruptible activities and uninterruptible tasks during their shifts. The work shifts of regular employees are often established several weeks in advance of the operations when the activity and task demands are still uncertain. Just a few days before the operations when these demands are unveiled with more certainty, the planned schedules can be slightly modified and on-call temporary employees can be scheduled to satisfy the demands as best as possible. As acceptable modifications, extending the planned shifts and moving workers’ meal breaks are considered. In this paper, we are interested in the scheduling problem encountered in this second step, which also involves assigning activities and tasks to the scheduled work shifts. To produce good-quality solutions in fast computational times for large-sized instances, we develop a two-phase heuristic. In the first phase, an approximate mixed-integer programming model is used to suggest temporary shifts and extensions to regular shifts and to schedule and assign tasks. In the second phase, a column-generation heuristic embedded in a rolling horizon procedure determines the final shifts and assigns activities to them. Computational results obtained on randomly generated instances are reported to evaluate the validity of the proposed solution method.     

A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem

The multi-activity multi-task shift scheduling problem requires the assignment of interruptible activities and uninterruptible tasks to a set of employees in order to satisfy a demand function. In this paper, we consider the personalized variant of the problem where the employees have different qualifications, preferences, and availabilities. We present a branch-and-price algorithm to solve this problem. The pricing subproblems in column generation are formulated with context-free grammars that are able to model complex rules in the construction of feasible shifts for an employee. We present results for a large set of instances inspired by real cases and show that this approach is sufficiently flexible to handle different classes of problems.     

An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-dependent setup times

In this paper the setup assembly line balancing and scheduling problem (SUALBSP) is considered. Since this problem is NP-hard, a hybrid genetic algorithm (GA) is proposed to solve the problem. This problem involves assigning the tasks to the stations and scheduling them inside each station. A simple permutation is used to determine the sequence of tasks. To determine the assignment of tasks to stations, the algorithm is hybridized using a dynamic programming procedure. Using dynamic programming, at any time a chromosome can be converted to an optimal solution (subject to the chromosome sequence).     

Robust assembly line balancing with heterogeneous workers

Assembly lines are manufacturing systems in which a product is assembled progressively in workstations by different workers or machines, each executing a subset of the needed assembly operations (or tasks). We consider the case in which task execution times are worker-dependent and uncertain, being expressed as intervals of possible values. Our goal is to find an assignment of tasks and workers to a minimal number of stations such that the resulting productivity level respects a desired robust measure. We propose two mixed-integer programming formulations for this problem and explain how these formulations can be adapted to handle the special case in which one must integrate a particular set of workers in the assembly line. We also present a fast construction heuristic that yields high quality solutions in just a fraction of the time needed to solve the problem to optimality. Computational results show the benefits of solving the robust optimization problem instead of its deterministic counterpart.     

A hybrid evolutionary algorithm for task scheduling and data assignment of data-intensive scientific workflows on clouds

A growing number of data- and compute-intensive experiments have been modeled as scientific workflows in the last decade. Meanwhile, clouds have emerged as a prominent environment to execute this type of workflows. In this scenario, the investigation of workflow scheduling strategies, aiming at reducing its execution times, became a top priority and a very popular research field. However, few work consider the problem of data file assignment when solving the task scheduling problem. Usually, a workflow is represented by a graph where nodes represent tasks and the scheduling problem consists in allocating tasks to machines to be executed at a predefined time aiming at reducing the makespan of the whole workflow. In this article, we show that the scheduling of scientific workflows can be improved when both task scheduling and the data file assignment problems are treated together. Thus, we propose a new workflow representation, where nodes of the workflow graph represent either tasks or data files, and define the Task Scheduling and Data Assignment Problem (TaSDAP), considering this new model. We formulated this problem as an integer programming problem. Moreover, a hybrid evolutionary algorithm for solving it, named HEA-TaSDAP, is also introduced. To evaluate our approach we conducted two types of experiments: theoretical and practical ones. At first, we compared HEA-TaSDAP with the solutions produced by the mathematical formulation and by other works from related literature. Then, we considered real executions in Amazon EC2 cloud using a real scientific workflow use case (SciPhy for phylogenetic analyses). In all experiments, HEA-TaSDAP outperformed the other classical approaches from the related literature, such as Min–Min and HEFT.     

Staff assignment with lexicographically ordered acceptance levels

Staff assignment is a compelling exercise that affects most companies and organizations in the service industries. Here, we introduce a new real-world staff assignment problem that was reported to us by a Swiss provider of commercial employee scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of critical and noncritical requests, including employees’ personal preferences. Each request has a target value, and deviations from the target value are associated with integer acceptance levels. These acceptance levels reflect the relative severity of possible deviations, e.g., for the request of an employee to have at least two weekends off, having one weekend off is preferable to having no weekend off and thus receives a higher acceptance level. The objective is to minimize the total number of deviations in lexicographical order of the acceptance levels. Staff assignment approaches from the literature are not applicable to this problem. We provide a binary linear programming formulation and propose a matheuristic for large-scale instances. The matheuristic employs effective strategies to determine the subproblems and focuses on finding good feasible solutions to the subproblems rather than proving their optimality. Our computational analysis based on real-world data shows that the matheuristic scales well and outperforms commercial employee scheduling software.     

A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation

This paper introduces the multi-activity combined timetabling and crew scheduling problem. The goal of this problem is to schedule the minimum number of workers required in order to successfully visit a set of customers characterized by services needed matched against schedule availability. Two solution strategies are proposed. The first is based on mathematical programming whilst the second uses a heuristic procedure in order to reduce computational time. The proposed model combines timetabling with crew scheduling decisions in one mixed integer programming model which considers multiple activities. The algorithms are tested on randomly generated and real instances provided by the Health to School Initiative, a program based at Bogotá’s local Health Department. The results show that the Initiative can increase its coverage by up to 68% using the proposed heuristic approach as a planning process tool.     

A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation

This paper introduces the multi-activity combined timetabling and crew scheduling problem. The goal of this problem is to schedule the minimum number of workers required in order to successfully visit a set of customers characterized by services needed matched against schedule availability. Two solution strategies are proposed. The first is based on mathematical programming whilst the second uses a heuristic procedure in order to reduce computational time. The proposed model combines timetabling with crew scheduling decisions in one mixed integer programming model which considers multiple activities. The algorithms are tested on randomly generated and real instances provided by the Health to School Initiative, a program based at Bogotá’s local Health Department. The results show that the Initiative can increase its coverage by up to 68% using the proposed heuristic approach as a planning process tool.     

An optimal allocation of memory buffers for complex multicore platforms

In deeply embedded heterogeneous multicores the allocation of data to memories is crucial for application performance. For applications with stringent throughput constraints, the allocation is often done manually by carefully assigning static memory locations to the logical buffers of the application. Today, designers are confronted with applications with thousands of buffers and architectures with hundreds of memories, rendering manual approaches impractical. In this paper we present an automatic approach for statically allocating logical buffers to physical memories, assuming a fixed task-to-processor mapping and respecting multiple throughput constraints.In our approach, we model the application in a data-centric way, by explicitly defining buffers and associating computational tasks that access the buffers within well-specified time intervals. Besides, we use an architecture model that allows to perform an allocation that is aware of the topology of the multicore and the physical bandwidth constraints of the interconnect. We present a layered approach to describe and solve the buffer-allocation problem as well as related subproblems, using mixed-integer linear programming. We show that the buffer-allocation problem is NP-complete, and present a more scalable formulation as a semi-definite programming problem. We evaluate the proposed LP methods by allocating around 1000 buffers corresponding to processing one frame in the Long-Term Evolution (LTE) standard, onto a multicore with 80 processing elements. We introduce a solution approach that allowed to find an optimal allocation in around 2 hours, which is at least two orders of magnitude faster than a straightforward formulation.     

An application of dynamic Nash task assignment strategies to multi-team military air operations

Dynamic task assignment is a critical issue in the control of dynamic systems that are controlled by a multi-team structure. In general, assigning a task to one team requires considering the actions taken by the other teams. An interesting example of dynamic task assignment is the deployment of resources such as in the case of teams of fighting units on each side during a military air operation. An initial deployment of resources and task assignments may not always result in the most desirable outcome. A reassignment of the units to different tasks during the course of operation may then become necessary in order to achieve the required objective. In this paper, the possibilities of changing the initial assignment of certain units, and the deployment of units after completing their initial assignment to other tasks are investigated. Two typical cases requiring specific reassignment strategies are considered. A simulation example of an air military operation that involves two opposing forces is presented to illustrate the results. In this example, the attacking force consists of two teams of units that need to complete two different tasks of varying complexity. Comparison of results with and without reassignment strategies is presented. We show that the use of reassignment strategies, especially when optimization is carried out over a short (two-step) look-ahead horizon, can improve the performance of the overall system and thus provide the leader of the attacking force with a more flexible and effective control mechanism to achieve the desired objective.     

A dispatching method for automated lifting vehicles in automated port container terminals

In automated container terminals, containers are transported from the marshalling yard to a ship and vice versa by automated vehicles. The automated vehicle type studied in this paper is an automated lifting vehicle (ALV) that is capable of lifting a container from the ground by itself. This study discusses how to dispatch ALVs by utilizing information about pickup and delivery locations and time in future delivery tasks. A mixed-integer programming model is provided for assigning optimal delivery tasks to ALVs. A procedure for converting buffer constraints into time window constraints and a heuristic algorithm for overcoming the excessive computational time required for solving the mathematical model are suggested. Numerical experiments are reported to compare the objective values and computational times by a heuristic algorithm with those by an optimizing method and to analyze the effects of dual cycle operation, number of ALVs, and buffer capacity on the performance of ALVs.     

求解炼钢连铸生产调度问题的改进算法

将炼钢连铸生产调度问题抽象为混和流水车间调度,建立了0-1型混合整数线性规划模型,并提出了一种遗传和线性规划相结合的求解方法。该模型通过优化钢水传搁时间来满足钢水的温度要求,通过最小化浇次开浇提前/拖期惩罚来协调连铸与热轧间的生产节奏。在算法设计中,给出了一种染色体编码来表示炉次设备指派与炉次在设备上的加工顺序方案,并探讨了相应的遗传操作。最后,仿真实验的结果表明了该算法的有效性。     

An exact algorithm for a Vehicle-and-Driver Scheduling Problem

This article introduces a combinatorial optimization problem that consists of assigning tasks to machines and operators, and sequencing the tasks assigned to each one. Two configurations exist. Machines alternate configurations, while the operators must start and finish the process in the same configuration. Moreover, machines and operator have limited capacities. The sequencing of the tasks must guarantee that each one is performed by a machine and an operator at the same time, and it is determined in order to minimize an overall cost function. Two critical aspects of the problem are the need of synchronizing the machine and the operator performing each task, and the need of minimizing the changeovers, which are pairs of tasks done consecutively by the same machine but by different operators. The problem is modeled as a vehicle routing problem with two types of vehicles and with two depots. We propose a mixed integer programming formulation, and introduce valid inequalities to strengthen its linear programming relaxation. We describe separation routines for these inequalities and design a branch-and-cut algorithm for the problem. The algorithm is tested on a set of benchmark instances showing that it is able to solve to optimality instances with up to 50 customers.     

Intruder alert! Optimization models for solving the mobile robot graph-clear problem

We develop optimization approaches to the graph-clear problem, a pursuit-evasion problem where mobile robots must clear a facility of intruders. The objective is to minimize the number of robots required. We contribute new formal results on progressive and contiguous assumptions and their impact on algorithm completeness. We present mixed-integer linear programming and constraint programming models, as well as new heuristic variants for the problem, comparing them to previously proposed heuristics. Our empirical work indicates that our heuristic variants improve on those from the literature, that constraint programming finds better solutions than the heuristics in run-times reasonable for the application, and that mixed-integer linear programming is superior for proving optimality. Given their performance and the appeal of the model-and-solve framework, we conclude that the proposed optimization methods are currently the most suitable for the graph-clear problem.     

A new heuristic branching scheme for the crew pairing problem with base constraints

Airline crew scheduling is typically performed in two steps : crew pairing followed by crew assignment. The crew pairing problem (CPP) finds a set of pairings (sequences of flights separated by connections or rests starting and ending at the same crew base) that covers a set of flights at minimum cost. The crew assignment problem consists of assigning the crew members to these pairings to create their individual schedules. The main downside of this sequential approach is that the pairings generated in the first step are not all suitable for the crew assignment step, yielding poor-quality solutions. This paper studies an extension of the CPP that includes additional constraints limiting the total worked time at each crew base. This problem, called the CPP with base constraints (CPPBC), is designed to improve the coupling of the two scheduling steps. To solve the CPPBC, we develop four branch-and-price heuristics: three of them rely on known heuristic branching schemes, the other introduces a new branching method, called retrospective branching. This branching scheme is designed to detect and revise poor branching decisions made earlier in the search tree, without backtracking. We tested and compared these four heuristics on real-world datasets. Our results show that the algorithm with retrospective branching yields, most of the times, better-quality solutions than the other tested methods.     

Task assignment using a problem-space genetic algorithm

The task assignment problem is one of assigning tasks of a parallel program among the processors of a distributed computing system in order to reduce the job turnaround time and to increase the throughput of the system. Since the task assignment problem is known to be NP-complete except in a few special situations, satisfactory suboptimal solutions obtainable in a reasonable amount of computation time are generally sought. In the paper we introduce a technique based on the problem-space genetic algorithm (PSGA) for the static task assignment problem in both homogeneous and heterogeneous distributed computing systems to reduce the task turnaround time and to increase the throughput of the system by properly balancing the load and reducing the interprocessor communication time among processors. The PSGA based approach combines the power of genetic algorithms, a global search method, with a simple and fast problem-specific heuristic to search a large solution space efficiently and effectively to find the best possible solution in an acceptable CPU time. Experimental results on test examples from the literature show considerable improvements in both the assignment cost and the CPU times over the previous work. The proposed scheme is also applied to a digital signal processing (DSP) system consisting of 119 tasks to illustrate its balancing properties and computational advantage on a large system. The proposed scheme offers 12–30% improvement in the assignment cost as compared to the previous best known results for the DSP example.     

New linearizations of quadratic assignment problems

New mixed-integer linear programming formulations are presented for the quadratic assignment problem, based on splittings of the coefficient matrices. Computational results are reported for medium-sized problem instances in the QAPLIB collection.