On a methodology for discrete–continuous scheduling

Discrete–continuous problems of scheduling nonpreemptable jobs on parallel machines are considered. The problems arise e.g. when jobs are assigned to multiple parallel processors driven by a common electric, hydraulic or pneumatic power source. Existing models have assumed job processing rates as a function of the number of jobs currently being processed, or equivalently the number of machines currently in operation. In this paper a more general model is proposed in which processing rates of a job assigned to a machine depend on the amount of a continuous, i.e. continuously divisible resource (e.g. power) allotted to this job at a time. Thus the problem consists of two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to allocate the continuous resource among jobs already sequenced. We provide a comprehensive analysis of the problem. This includes properties of optimal schedules, efficiently (in particular analytically) solvable cases, formulations of the possibly simplest mathematical programming problems for finding optimal schedules in the general case, heuristics and the worst-case analysis. Although our objective function in this paper is to minimize makespan of a set of independent jobs, the presented methodology can be applied to other criteria, precedence-related jobs, and many resource types (apart from, or instead of machines).     

Scheduling parallel machines with inclusive processing set restrictions and job release times

We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed.     

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.     

Parallel machine scheduling with a common due window

In this paper, we consider a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized. Specifically, we consider the problem with a set of independent jobs to be processed on several identical parallel machines. All the jobs have a given common due window. If a job is completed within the due window, then there is no penalty. Otherwise, there is either a job-dependent earliness penalty or a job-dependent tardiness penalty depending on whether the job is completed before or after the due window. The objective is to find an optimal schedule with minimum total earliness–tardiness penalty. The problem is known to be NP-hard. We propose a branch and bound algorithm for finding an optimal schedule of the problem. The algorithm is based on the column generation approach in which the problem is first formulated as a set partitioning type formulation and then in each branch and bound iteration the linear relaxation of this formulation is solved by the standard column generation procedure. Our computational experiments show that this algorithm is capable of solving problems with up to 40 jobs and any number of machines within a reasonable computational time.     

带批运输的两台同型机排序问题的改进算法

研究带批运输的两台同型机排序问题. 在该问题中,工件在两台同型机上加工,完工的工件由一辆容量为z的车运输到客户. 这里假设工件有不同的物理大小,目标是求一个时间表使得所有工件送达客户且车回到机器所在位置的时间最小,给出了一个(14/9+ε)-近似算法     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop

This paper considers the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. It continues recent work by Bräsel et al. [H. Bräsel, A. Herms, M. Mörig, T. Tautenhahn, T. Tusch, F. Werner, Heuristic constructive algorithms for open shop scheduling to minmize mean flow time, European J. Oper. Res., in press (doi.10.1016/j.ejor.2007.02.057)] on constructive algorithms. For this strongly NP-hard problem, we present two iterative algorithms, namely a simulated annealing and a genetic algorithm. For the simulated annealing algorithm, several neighborhoods are suggested and tested together with the control parameters of the algorithm. For the genetic algorithm, new genetic operators are suggested based on the representation of a solution by the rank matrix describing the job and machine orders. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The algorithms are compared relative to each other, and the quality of the results is also estimated partially by a lower bound for the corresponding preemptive open shop problem. For most of the problems, the genetic algorithm is superior when fixing the same number of 30 000 generated solutions for each algorithm. However, in contrast to makespan minimization problems, where the focus is on problems with an equal number of jobs and machines, it turns out that problems with a larger number of jobs than machines are the hardest problems.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Scheduling incompatible tasks on two machines

The paper studies the problem of scheduling tasks on two machines to minimize the makespan. The tasks are assigned to the machine in advance. An incompatibility relation is defined over the tasks which forbids any two incompatible tasks to be processed at the same time. The problem can serve as a mathematical model for some batching problems in which the jobs are grouped in pairs on two machines. A linear-time algorithm is presented.     

Resolution of a scheduling problem in a flowshop robotic cell

We develop in this paper a generic and precise identification of a scheduling problem in a flexible manufacturing system. We consider a flowshop robotic cell that processes several jobs. We assume that there is no intermediate buffer between machines. So, jobs may be blocked when downstream machines are busy. We present an integer programming model to determine the sequence of jobs that minimizes the makespan criterion. In order to solve large size problems, we propose a genetic algorithm (GA). Finally, computational experiments are proposed in order to compare the makespan returned by the GA to a lower bound.     

Specially Structured Precedence Constraints in Three-Dimensional Bottleneck Assignment Problems

A three-dimensional, time-minimizing (bottleneck) assignment problem consists of assigning n jobs to n workers to be performed on n machines under different forms of feasibility conditions so that the different functions of the individual times taken by a worker to finish a job on a given machine are minimized. The usual assumption made in such a problem is that all the jobs can be commenced simultaneously. In this paper, two specially structured precedence constraints on jobs are considered, which necessitate modifications in this assumption. Further, the main purpose here is to develop branch-and-bound-type algorithms for solving the corresponding problems and to illustrate them by a numerical example.     

Local search metaheuristics for discrete–continuous scheduling problems

Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource are considered. For each job there are known: its processing speed as a continuous, concave function of a continuous resource allotted at a time and its processing demand. The optimization criterion is the schedule length. The problem can be decomposed into two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to find an optimal (continuous) resource allocation among jobs already sequenced. Problem (ii) can be formulated as a convex programming problem with linear constraints and solved using proper solvers. Thus, the problem remains to generate a set of all feasible sequences of jobs on machines (this guarantees finding an optimal schedule in the general case). However, the cardinality of this set grows exponentially with the number of jobs. Thus, we propose to use heuristic search methods defined on the space of feasible sequences. Three metaheuristics: tabu search (TS), simulated annealing (SA) and genetic algorithm (GA) have been implemented and compared computationally with a random sampling technique. The computational experiment has been carried out on an SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out.     

Minimizing total tardiness in an unrelated parallel-machine scheduling problem

We consider a problem of scheduling n independent jobs on m unrelated parallel machines with the objective of minimizing total tardiness. Processing times of a job on different machines may be different on unrelated parallel-machine scheduling problems. We develop several dominance properties and lower bounds for the problem, and suggest a branch and bound algorithm using them. Results of computational experiments show that the suggested algorithm gives optimal solutions for problems with up to five machines and 20 jobs in a reasonable amount of CPU time.     

机器具有优势关系下的工件加工时间可控的流水作业排序问题

本文主要研究机器具有优势关系下的工件加工时间可控的流水作业排序问题.我们主要对以下两种情形进行了讨论:工件加工时间为线性恶化和线性学习.对于每一种加工模型,我们分别研究了几类不同的优势机器,并且对每种情况均给出了多项式时间算法.     

具有特殊工件的平行机在线排序问题

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686.     

Formulating and solving production planning problems

Production planning problems frequently involve the assignment of jobs or operations to machines. The simplest model of this problem is the well known assignment problem (AP). However, due to simplifying assumptions this model does not provide implementable solutions for many actual production planning problems. Extensions of the simple assignment model known as the generalized assignment problem (GAP) and the multi-resource generalized assignment problem (MRGAP) have been developed to overcome this difficulty. This paper presents an extension of the (MRGAP) to allow splitting individual batches across multiple machines, while considering the effect of setup times and setup costs. The extension is important for many actual production planning problems, including ones in the injection molding industry and in the metal cutting industry. We formulate models which are logical extensions of previous models which ignored batch splitting for the problem we address. We then give different formulations and suggest adaptations of a genetic algorithm (GA) and simulated annealing (SA). A systematic evaluation of these algorithms, as well as a Lagrangian relaxation (LR) approach, is presented.     

The Systems Approach to Hospitals

By exploiting the relationship between scheduling and sorting, this paper describes a functional heuristic algorithm for seeking a quick and approximate solution to the n-job, M-machine flowshop scheduling problem under the assumption that all jobs are processed on all machines in the same order and no passing of jobs is permitted. The proposed functional heuristic algorithm can be executed by hand for reasonably large size problems and yields solutions which are closer to optimal solutions than those obtained by Palmer's slope index algorithm.     

Scheduling on parallel identical machines to minimize total tardiness

This paper focuses on the problem of scheduling n independent jobs on m identical parallel machines for the objective of minimizing total tardiness of the jobs. We develop dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as upper bounds obtained from a heuristic algorithm. Computational experiments are performed on randomly generated test problems and results show that the algorithm solves problems with moderate sizes in a reasonable amount of computation time.     

A branch and bound algorithm for the two-stage assembly scheduling problem

This paper develops a branch and bound algorithm for the two-stage assembly scheduling problem. In this problem, there are m machines at the first stage, each of which produces a component of a job. When all m components are available, a single assembly machine at the second stage completes the job. The objective is to schedule the jobs on the machines so that the maximum completion time, or makespan, is minimized. A lower bound based on solving an artificial two-machine flow shop problem is derived. Also, several dominance theorems are established and incorporated into the branch and bound algorithm. Computational experience with the algorithm is reported for problems with up to 8000 jobs and 10 first-stage machines.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.