Setup times and fast tracking in resource-constrained project scheduling

Resource-constrained project scheduling with activity pre-emption assumes that activities are allowed to be interrupted and restarted later in the schedule at no extra cost. In the current paper, we extend this pre-emptive scheduling problem with setup times between activity interruptions and the possibility to schedule pre-emptive sub-parts of activities in parallel.

The contribution of the paper is twofold. First, we briefly show that an efficient exact branch-and-bound procedure from the literature to solve the resource-constrained project scheduling problem can be easily adapted to cope with our problem extensions. Second, we extensively test the impact of these pre-emptive extensions to the quality of the schedule from a makespan point-of-view.     

Resource-constrained flowshop scheduling with separate resource recycling operations

This paper considers the relocation problem arising from public re-development projects cast as a two-machine flowshop scheduling problem. In such a project, some buildings need to be torn down and re-constructed. The two processes of tearing down and re-constructing each building are often viewed as a single operation. However, under certain circumstances, the re-construction process, i.e., the resource recycling process, can be viewed as a separate operation. In this paper we regard these two processes as separate on the assumption that they are handled by different working crews. We formulate the problem as a resource-constrained two-machine flowshop scheduling problem with the objective of finding a feasible re-development sequence that minimizes the makespan. We provide problem formulations, discuss the complexity results, and present polynomial algorithms for various special cases of the problem.     

Time-constrained project scheduling with adjacent resources

We develop a decomposition method for the Time-Constrained Project Scheduling Problem (TCPSP) with adjacent resources. For adjacent resources the resource units are ordered and the units assigned to a job have to be adjacent. On top of that, adjacent resources are not required by single jobs, but by job groups. As soon as a job of such a group starts, the adjacent resource units are occupied, and they are not released before all jobs of that group are completed. The developed decomposition method separates the adjacent resource assignment from the rest of the scheduling problem. Test results demonstrate the applicability of the decomposition method. The presented decomposition forms a first promising approach for the TCPSP with adjacent resources and may form a good basis to develop more elaborated methods.     

A note on “the capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times

Gupta and Magnusson [The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times. Computers and Operations Research 2005;32(4):727–47] develop a model for the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence dependent setup times and setup costs, incorporating all the usual features of setup carryovers. In this note we show that this model does not avoid disconnected subtours. A new set of constraints is added to the model to provide an exact formulation for this problem.     

Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.     

A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times

This paper introduces and compares three different formulations of a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The setup is divided into two parts: one that can be performed at any time and another one that is restricted to be performed outside of a given time interval. As a result, the setup time between two jobs is a function of the completion time of the first job. The problem can be formulated as a time-dependent traveling salesman problem, where the travel time between two nodes is a function of the departure time from the first node. We show that the resulting formulation can be strengthened to provide better linear programming relaxation lower bounds. We also introduce several families of valid inequalities which are used within a branch-and-cut algorithm. Computational experiments show that this algorithm can solve some instances with up to 50 jobs within reasonable computing times.     

Single machine batch scheduling to minimize total completion time and resource consumption costs

In this paper we study the single-machine batch scheduling problem under batch availability, where both setup and job processing times are controllable by allocating a continuously divisible nonrenewable resource. Under batch availability a set of jobs is processed contiguously and completed together, when the processing of the last job in the batch is finished. We present polynomial time algorithms to find the job sequence, the partition of the job sequence into batches and the resource allocation, which minimize the total completion time or the total production cost (inventory plus resource costs).     

Project scheduling under resource constraints: Application of the cumulative global constraint in a decision support framework

This paper concerns project scheduling under resource constraints. Traditionally, the objective is to find a unique solution that minimizes the project makespan, while respecting the precedence constraints and the resource constraints. This work focuses on developing a model and a decision support framework for industrial application of the cumulative global constraint. For a given project scheduling, the proposed approach allows the generation of different optimal solutions relative to the alternate availability of outsourcing and resources. The objective is to provide a decision-maker an assistance to construct, choose, and define the appropriate scheduling program taking into account the possible capacity resources. The industrial problem under consideration is modeled as a constraint satisfaction problem (CSP). It is implemented under the constraint programming language CHIP V5. The provided solutions determine values for the various variables associated to the tasks realized on each resource, as well as the curves with the profile of the total consumption of resources on time.     

Variable assignment and instruction scheduling for processor with multi-module memory

Multi-module memory has been employed in high-end digital signal processing system (DSP). It provides high memory bandwidth and low power operating mode for energy savings. However, making full use of these architectural features is a challenging problem for code optimization. In this paper, we propose an integer linear programming (ILP) model to optimize the performance and energy consumption of multi-module memories by solving variable assignment, instruction scheduling and operating mode setting problems simultaneously. The combined effect of performance and energy saving requirements has been considered as well. Specially, we develop two optimization techniques to improve the computation efficiency of our ILP model. The experimental results show that the optimal performance and energy solution can be achieved within a reasonable amount of time.     

Fast reactive scheduling to minimize tardiness penalty and energy cost under power consumption uncertainties

Motivated by the need to deal with uncertainties in energy optimization of flexible manufacturing systems, this paper considers a dynamic scheduling problem which minimizes the sum of energy cost and tardiness penalty under power consumption uncertainties. An integrated control and scheduling framework is proposed including two modules, namely, an augmented discrete event control (ADEC) and a max-throughput-min-energy reactive scheduling model (MTME). The ADEC is in charge of inhibiting jobs which may lead to deadlocks, and sequencing active jobs and resources. The MTME ensures the fulfillment of the innate constraints and decides the local optimal schedule of active jobs and resources. Our proposed framework is applied to an industrial stamping system with power consumption uncertainties formulated using three different probability distributions. The obtained schedules are compared with three dispatching rules and two rescheduling approaches. Our experiment results verify that MTME outperforms three dispatching rules in terms of deviation from Pareto optimality and reduces interrupted time significantly as compared to rescheduling approaches. In addition, ADEC and MTME are programmed using the same matrix language, providing easy implementation for industrial practitioners.     

A bicriteria approach to minimize maximal lateness and resource consumption for scheduling a single machine

We extend the classical single-machine maximal lateness scheduling problem to the case where the job processing times are controllable by allocating a continuous and nonrenewable resource to the processing operations. Our aim is to construct an efficient trade-off curve between maximal lateness and total resource consumption using a bicriteria approach. We present a polynomial time algorithm that constructs this trade-off curve assuming a specified general type of convex decreasing resource consumption function. We illustrate the algorithm with a numerical example.     

Yard crane scheduling in a container terminal for the trade-off between efficiency and energy consumption

Green transportation has recently been the focus of the transportation industry to sustain the development of global economy. Container terminals are key nodes in the global transportation network and energy-saving is a main goal for them. Yard crane (YC), as one type of handling equipment, plays an important role in the service efficiency and energy-saving of container terminals. However, traditional methods of YC scheduling solely aim to improve the efficiency of container terminals and do not refer to energy-saving. Therefore, it is imperative to seek an appropriate approach for YC scheduling that considers the trade-off between efficiency and energy consumption. In this paper, the YC scheduling problem is firstly converted into a vehicle routing problem with soft time windows (VRPSTW). This problem is formulated as a mixed integer programming (MIP) model, whose two objectives minimize the total completion delay of all task groups and the total energy consumption of all YCs. Subsequently, an integrated simulation optimization method is developed for solving the problem, where the simulation is designed for evaluating solutions and the optimization algorithm is designed for exploring the solution space. The optimization algorithm integrates the genetic algorithm (GA) and the particle swarm optimization (PSO) algorithm, where the GA is used for global search and the PSO is used for local search. Finally, computational experiments are conducted to validate the performance of the proposed method.     

Heuristics for the minimum project-duration problem with minimal and maximal time lags under fixed resource constraints

The authors consider the problem of minimizing the duration of a project under fixed resource constraints. For the case that there are only minimal time lags between the start of successive activities and that therefore the project can be described by an acyclic network, a large number of exact and heuristic algorithms can be found in the literature. In this paper, the authors permit both minimal and maximal time lags between activities. The project can then be modelled by an activityon-node network containing cycles. Efficient priority-rule heuristics are presented for solving the resource-constrained project-scheduling problem. Computational results are discussed for projects containing up to 1000 activities and several resources.