A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration

This paper addresses the integration of two emerging classes of scheduling problems which, for the most part, have evolved independently. These problem classes are (i) scheduling problems with time-dependent processing times and (ii) scheduling problems with rate-modifying activities (RMAs). The integration of these two concepts is motivated by human operators who experience fatigue while carrying out tasks and take rest breaks for recovery, but is also applicable to machines that experience performance degradation over time and require maintenance in order to sustain acceptable production rates. We explore a sequence-independent, single processor makespan problem with position-dependent processing times and prove that under certain conditions, the optimal policy is to schedule the RMA in the middle of the task sequence.     

A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints

We address a generalization of the classical 1- and 2-processor unit execution time scheduling problem on dedicated machines. In our chromatic model of scheduling machines have non-simultaneous availability times and tasks have arbitrary release times and due dates. Also, the versatility of our approach makes it possible to generalize all known classical criteria of optimality. Under these stipulations we show that the problem of optimal scheduling of sparse tree-like instances can be solved in polynomial time. However, if we admit dense instances then the problem becomes NP-hard, even if there are only two machines.     

Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.     

An approach to solve the minimum expected makespan flow-shop problem subject to breakdowns

Daily, there are multiple situations where machines or workers must execute certain jobs. During a working day it may be that some workers or machines are not available to perform their activities during some time periods. When scheduling models are used in these situations, workers or machines are simply called “machines”, and the temporal absences of availability are known as “breakdowns”. This paper considers some of these cases studying stochastic scheduling models with several machines to perform activities. Machines are specialized and models are flow-shops where breakdowns are allowed. The paper proposes a general procedure that tries to solve these problems. The proposed approach converts breakdowns scheduling problems into a finite sequence of without-breakdowns problems. Thus, we consider random variables, which measure the length of availability periods and repair times, to study availability intervals of machines. We propose partial feasible schedules in these intervals and combine them to offer a final global solution to optimize the expected makespan. Computational experiences are also reported.     

Bilevel programming approach applied to the flow shop scheduling problem under fuzziness

This paper presents a fuzzy bilevel programming approach to solve the flow shop scheduling problem. The problem considered here differs from the standard form in that operators are assigned to the machines and imposing a hierarchy of two decision makers with fuzzy processing times. The shop owner considered higher level and assigns the jobs to the machines in order to minimize the flow time while the customer is the lower level and decides on a job schedule in order to minimize the makespan. In this paper, we use the concepts of tolerance membership function at each level to define a fuzzy decision model for generating optimal (satisfactory) solution for bilevel flow shop scheduling problem. A solution algorithm for solving this problem is given. Mathematics Subject Classification: 90C70, 90B36, 90C99     

A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines

The paper proposes a Mixed Integer Programming (MIP) formulation of the scheduling problem with total flow criterion on a set of parallel unrelated machines under an uncertainty context about the processing times. To model the problem we assume that lower and upper bounds are known for each processing time. In this context we consider an optimal minmax regret schedule as a suitable approximation to the optimal schedule under an arbitrary choice of the possible processing times.     

Scheduling preparation of doses for a chemotherapy service

A fast realization of drugs is an important part in the quality of service of a hospital. In this paper we propose a scheduling method for the preparation of chemotherapy doses in order to reduce the patient waiting time. Two approaches have been defined: an off-line approach and a real time approach. The off-line approach is using a linear programming model for minimizing the maximum tardiness of jobs in a production day. This method is re-used during the real-time resolution combined with a greedy algorithm. The solution obtained respects constraints on the production center and the hospital organization. Our model is currently used in software which helps the decision maker of the service and allows increasing the patient satisfaction and the productivity of the service.     

A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital

Publicly-funded hospitals are typically allocated an annual budget by the government based on the number of enrollees in the region. Given tight budget constraints, the capacity of resources is fairly fixed. Such hospitals strive to maximize the utilization of their resources through continuous improvement and optimization techniques. We address a surgical case scheduling problem experienced at a publicly-funded hospital and conceptualize this multi-period, multi-resource, priority-based case scheduling problem as an unequal-sized, multi-bin, multi-dimensional dual bin-packing problem. A mixed integer programming model and a heuristic based on the first fit decreasing algorithm are presented. Resource availability, case priorities, and variation in surgery times are key features included in our model. Our proposed approach led to substantial savings, 20% reduction in number of days and up to 20% increase in operating room utilization, when compared to real schedules obtained from the surgical department at a publicly-funded hospital.     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

Scheduling project networks with resource constraints and time windows

Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.We consider the problem to schedule such networks subject to arbitrary (even time dependent) resource constraints in order to minimize an arbitrary regular performance measure (i.e. a non-decreasing function of the vector of completion times). This problem arises in many standard industrial construction or production processes and is therefore particularly suited as a background model in general purpose decision support systems.The treatment is done by a structural approach that involves a generalization of both the disjunctive graph method in job shop scheduling [1] and the order theoretic methods for precedence constrained scheduling [18,23,24]. Besides theoretical insights into the problem structure, this approach also leads to rather powerful branch-and-bound algorithms. Computational experience with this algorithm is reported.     

Robust scheduling of parallel machines with sequence-dependent set-up costs

In this paper we propose a robust approach for solving the scheduling problem of parallel machines with sequence-dependent set-up costs. In the literature, several mathematical models and solution methods have been proposed to solve such scheduling problems, but most of which are based on the strong assumption that input data are known in a deterministic way. In this paper, a fuzzy mathematical programming model is formulated by taking into account the uncertainty in processing times to provide the optimal solution as a trade-off between total set-up cost and robustness in demand satisfaction. The proposed approach requires the solution of a non-linear mixed integer programming (NLMIP), that can be formulated as an equivalent mixed integer linear programming (MILP) model. The resulting MILP model in real applications could be intractable due to its NP-hardness. Therefore, we propose a solution method technique, based on the solution of an approximated model, whose dimension is remarkably reduced with respect to the original counterpart. Numerical experiments conducted on the basis of data taken from a real application show that the average deviation of the reduced model solution over the optimum is less than 1.5%.     

Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs

This paper studies the parallel machines bi-criteria scheduling problem (PMBSP) in a deteriorating system. Sequencing and scheduling problems (SSP) have seldom considered the two phenomena concurrently. This paper discusses the parallel machines scheduling problem with the effects of machine and job deterioration. By the machine deterioration effect, we mean that each machine deteriorates at a different rate. This deterioration is considered in terms of cost which depends on the production rate, the machine’s operating characteristics and the kind of work done by each machine. Moreover, job processing times are increasing functions of their starting times and follow a simple linear deterioration. The objective functions are minimizing total tardiness and machine deteriorating cost. The problem of total tardiness on identical parallel machines is NP-hard, thus the problem with machine deteriorating cost as an additional term is also NP-hard. We propose the LP-metric method to show the importance of our proposed multi-objective problem. A metaheuristic algorithm is developed to locate optimal or near optimal solutions based on a Tabu search mechanism. Numerical examples are presented to show the efficiency of this model.     

LP-based online scheduling: from single to parallel machines

We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice. A preliminary version of this work appears in the Proceedings of the 11th conference on integer programming and combinatorial optimization (IPCO), Berlin, 8–10 June 2005.     

Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties

In this paper we consider identical parallel machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remain polynomially solvable under the proposed model.     

Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops

In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures.     

A note on “A mixed integer programming model for advanced planning and scheduling (APS)”

In a recent paper, Chen and Ji [Chen, K., Ji, P., 2007. A mixed integer programming model for advanced planning and scheduling (APS). European Journal of Operational Research 181, 515–522] develop a mixed integer programming model for advanced planning and scheduling problem that considers capacity constraints and precedence relations between the operations. The orders require processing of several operations on eligible machines. The model presented in the above paper works for the case where each operation can be processed on only one machine. However, machine eligibility means that only a subset of machines are capable of processing a job and this subset may include more than one machine. We provide a general model for advanced planning and scheduling problems with machine eligibility. Our model can be used for problems where there are alternative machines that an operation can be assigned to.     

Integrated machine scheduling and vehicle routing with time windows

This paper integrates production and outbound distribution scheduling in order to minimize total tardiness. The overall problem consists of two subproblems. The first addresses scheduling a set of jobs on parallel machines with machine-dependent ready times. The second focusses on the delivery of completed jobs with a fleet of vehicles which may differ in their loading capacities and ready times. Job-dependent processing times, delivery time windows, service times, and destinations are taken into account. A genetic algorithm approach is introduced to solve the integrated problem as a whole. Two main questions are examined. Are the results of integrating machine scheduling and vehicle routing significantly better than those of classic decomposition approaches which break down the overall problem, solve the two subproblems successively, and merge the subsolutions to form a solution to the overall problem? And if so, is it possible to capitalize on these potentials despite the complexity of the integrated problem? Both questions are tackled by means of a numerical study. The genetic algorithm outperforms the classic decomposition approaches in case of small-size instances and is able to generate relatively good solutions for instances with up to 50 jobs, 5 machines, and 10 vehicles.     

Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time

This paper investigates scheduling problems with simultaneous considerations of deterioration effects and deteriorating multi-maintenance activities on unrelated parallel machines. We examine two models of scheduling with the deterioration effect, namely the job-dependent and position-dependent deterioration model and the time-dependent deterioration model. We assume that each machine may be subject to several maintenance activities over the scheduling horizon, and the duration of maintenance on a machine depends on its running time. Moreover, due to the restriction of the budget of maintenance, the upper bound of the total maintenance frequencies on all the machines is assumed to be known in advance. The objective is to find jointly the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequences such that the total completion time is minimized. If the number of machines is fixed, we introduce polynomial time solutions for all the versions of the problem under study.     

A new AATP model with considering supply chain lead-times and resources and scheduling of the orders in flowshop production systems: A graph-theoretic view

The present study attempts to synchronize the scheduling problem with determining the advanced available-to-promise (AATP) in a flowshop system to enhance supplier profitability and service level. In the proposed model the AATP, scheduling and graph theory concept have been combined to find the optimum resource allocation and enable accurate estimations of machines scheduling, production costs and delivery dates. To find the near optimum solutions for the large size problems a genetic algorithm is developed, first the orders are ranked based on their scores which are estimated then the optimum cost is calculated by balancing profitability and constraints such as the availability of the machines or the available material in each workstation. Some computer simulated experiments are provided to evaluate the performance of the proposed algorithm.