Generalization of Johnson's and Talwar's scheduling rules in two-machine stochastic flow shops

The paper deals with the classical problem of minimizing the makespan in a two-machine flow shop. When the job processing times are deterministic, the optimal job sequence can be determined by applying Johnson's rule. When they are independent and exponential random variables, Talwar's rule yields a job sequence that minimizes the makespan stochastically. Assuming that the random job processing times are independent and Gompertz distributed, we propose a new scheduling rule that is a generalization of both Johnson's and Talwar's rules. We prove that our rule yields a job sequence that minimizes the makespan stochastically. Extensions to m-machine proportionate stochastic flow shops, two-machine stochastic job shops, and stochastic assembly systems are indicated.     

Feasible insertions in job shop scheduling,short cycles and stable sets

Insertion problems arise in scheduling when additional activities have to be inserted into a given schedule. This paper investigates insertion problems in a general disjunctive scheduling framework capturing a variety of job shop scheduling problems and insertion types. First, a class of scheduling problems is introduced, characterized by disjunctive graphs with the so-called short cycle property, and it is shown that in such problems, the feasible selections correspond to the stable sets of maximum cardinality in an associated conflict graph. Two types of insertion problems are then identified where the underlying disjunctive graph is through- or bi-connected. For these cases, it is shown that the short cycle property holds and the conflict graph is bipartite, allowing to derive a polyhedral characterization of all feasible insertions. An efficient method for deciding whether there exists a feasible insertion, and a lower and upper bound procedure for the minimum makespan insertion problem are developed. For bi-connected graphs, this procedure solves the insertion problem to optimality. The obtained results are applied to three extensions of the classical Job Shop, the Multi-Processor Task, Blocking and No-Wait Job Shop, and two types of insertions, job and block insertion.     

A note on the flow time and the number of tardy jobs in stochastic open shops

In this note open shops with two machines are considered. The processing time of job j, j = 1, …, n, on machine 1 (2) is a random variable X_j (Y_j), which is exponentially distributed with rate γ (μ). If the completion time of job j is C_j, a waiting cost is incurred of g(C_j), where g is a function that is increasing concave. The preemptive policy that minimizes the total expected waiting cost E(Σg(C_j)) is determined. Two machine open shops with jobs that have random due dates are considered as well. For the case where the due dates D₁,…,D_n are exchangeable, the preemptive policy that minimizes the expected number of tardy jobs is determined.     

New approaches to due date assignment in job shops

In this study, two new approaches for due date assignment in job shops are evaluated. Proposed approaches use statistical prediction techniques for dynamic prediction of job flowtimes in a job shop environment as the job arrives to the shop floor. Primary objective of this research is to compare the performance of the proposed due date assignment model (PDDAM) with several conventional due date assignment models (CDDAM). For this purpose, simulation models are developed and comparisons of the PDDAM and CDDAM are made in terms of the mean absolute percent error (MAPE), mean percent error (MPE) and mean tardiness (MT). Simulation experiments showed that for many test conditions, PDDAM dominates CDDAM. Therefore, case by case findings are summarized in the paper.     

Scheduling jobs with release dates and tails on identical machines to minimize the makespan

This paper considers the problem of scheduling independent jobs with release dates and tails on m identical machines to minimize the makespan. This m-machines problem is NP-hard in the strong sense. Jackson's schedule is defined as the list schedule built by giving priority to the available job with the largest tail. It is proved that the deviation of Jackson's schedule from the optimum is smaller than twice the largest processing time.Next, a new branching scheme is proposed by associating with each job an interval of time during which it has to be processed. To branch, the interval for a particular job is divided into two smaller ones. This is a general scheme which can be applied to many scheduling problems.Finally, a branch and bound algorithm is explained in detail and computational results are given.     

Resource-constrained job scheduling with recyclable resources

In resource-constrained project scheduling problems, resources are typically classified as being either renewable, non-renewable, or doubly-constrained. A new resource classification, recyclable, is introduced. Notation and a generalized problem formulation are developed for resource-constrained job scheduling problems where resources are recyclable. This foundation is then used for studying the single-machine scheduling problem with tooling constraints. For a given set of jobs, the problem is to find the job sequence, tool type quantities, and tool recycling schedule such that the sum of job completion times and quantity of tools allocated are both minimized. Two solution approaches are developed, and examples are used to compare and contrast the approaches. The results indicate that the ‘traditional’ job scheduling approach (i.e. schedule jobs first, then tools) can lead to sub-optimal solutions. Furthermore, by scheduling jobs and tools simultaneously, it may be possible to attain a given level of performance with fewer tools.     

Coordination mechanisms for parallel machine scheduling

We consider coordination mechanisms for the distributed scheduling of n jobs on m parallel machines, where each agent holding a job selects a machine to process his/her own job. Without a central authority to construct a schedule, each agent acts selfishly to minimize his/her own disutility, which is either the completion time of the job or the congestion time (defined as the load of the machine on which the job is scheduled). However, the overall system performance is measured by a central objective which is quite different from the agents’ objective. In the literature, makespan is often considered as the central objective. We, however, investigate problems with other central objectives that minimize the total congestion time, the total completion time, the maximum tardiness, the total tardiness, and the number of tardy jobs. The performance deterioration of the central objective by a lack of central coordination, referred to as the price of anarchy, is typically measured by the maximum ratio of the objective function value of a Nash equilibrium schedule versus that of an optimal, coordinated schedule. In this paper we give bounds for the price of anarchy for the above objectives. For problems with due date related objectives, the price of anarchy may not be defined since the optimal value may be zero. In this case, we consider the maximum difference between the objective function value of an equilibrium schedule and the optimal value. We refer to this metric as the absolute price of anarchy and analyze its lower and upper bounds.     

On the complexity of scheduling unrelated parallel machines with limited preemptions

We consider the problem of finding a minimum-length preemptive schedule for n jobs on m parallel machines. The problem is solvable in polynomial time, whether the machines are identical, uniform or unrelated. For identical or uniform machines, it is easy to obtain an optimal schedule in which the portion of a job that is assigned to a single machine is processed without interruption. We show that imposing this condition in the case of unrelated machines makes the problem NP-hard.     

Polynomial time approximation schemes for general multiprocessor job shop scheduling

We study preemptive and non-preemptive versions of the general multiprocessor job shop scheduling problem: Given a set of n tasks each consisting of at most μ ordered operations that can be processed on different (possibly all) subsets of m machines with different processing times, compute a schedule (preemptive or non-preemptive, depending on the model) with minimum makespan where operations belonging to the same task have to be scheduled according to the specified order. We propose algorithms for both preemptive and non-preemptive variants of this problem that compute approximate solutions of any positive ε accuracy and run in O(n) time for any fixed values of m, μ, and ε. These results include (as special cases) many recent developments on polynomial time approximation schemes for scheduling jobs on unrelated machines, multiprocessor tasks, and classical open, flow and job shops.     

Due-window assignment with identical jobs on parallel uniform machines

A scheduling problem with a common due-window, earliness and tardiness costs, and identical processing time jobs is studied. We focus on the setting of both (i) job-dependent earliness/tardiness job weights and (ii) parallel uniform machines. The objective is to find the job allocation to the machines and the job schedule, such that the total weighted earliness and tardiness cost is minimized. We study both cases of a non-restrictive (i.e. sufficiently late), and a restrictive due-window. For a given number of machines, the solutions of the problems studied here are obtained in polynomial time in the number of jobs.     

On no-wait and no-idle flow shops with makespan criterion

The paper deals with the NP-hard problems of minimizing the makespan in m-machine no-wait and no-idle permutation flow shops. We identify networks whose longest path lengths represent the makespans. These networks reveal the duality between the two problems, and show graphical explanations of the fact that under no-wait and no-idle conditions the makespan can be a decreasing function of some job processing times. Moreover, they also lead to a natural reduction of the no-wait flow shop problem to the traveling salesman problem, some lower bounds on the shortest makespan, and new efficiently solvable special cases.     

Scheduling unit — time tasks on flow — shops under resource constraints

We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is proved that when the number of machines is arbitrary, the problem of minimizing schedule length is NP-hard, even when only one unit of the additional resource is available in the system. On the other hand, when the number of machines is fixed, then the problem is solvable in polynomial time, even for an arbitrary number of resource units available. For the two machine case anO(n log ₂ ² n) algorithm minimizing maximum lateness is also given. The presented results are also of importance in some message transmission systems.     

Scheduling independent jobs for torus connected networks with/without link contention

In this paper, we investigate the problem of how to schedule n independent jobs on an m × m torus based network. We develop a model to to quantify the effect of contention for communication links on the dilation of job execution time when multiple jobs share communication links; we then design an efficient algorithm to schedule a set of n independent jobs with different torus size requirements on a given torus with an objective to minimize the total schedule length. We also develop a feasibility algorithm for pre-emptively scheduling a given set of jobs on a torus of given size with a given deadline. We provide analysis for both the algorithms.     

A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times

We consider the problem of scheduling independent jobs on a single resource under a special unavailability constraint: a set of forbidden instants is given, where no job is allowed to start or complete. We show that a schedule without idle time always exists if the number of forbidden instants is less than the number of distinct processing times appearing in the instance. We derive quite a fast algorithm to find such a schedule, based on an hybridization between a list algorithm and local exchange. As a corollary minimizing the makespan for a fixed number of forbidden instants is polynomial.     

The constrained minimum weighted sum of job completion times problem

We consider the problem of minimizing the weighted sum of job completion times on a single machine (subject to certain job weights) with an additional side constraint on the weighted sum of job completion times (with respect to different job weights). This problem is NP-hard, and we provide a polynomial time approximation scheme for this problem. Our method is based on Lagrangian relaxation mixed with carefully guessing the positions of certain jobs in the schedule. An earlier version of this paper appeared in the Proceedings of the 10th International IPCO Conference.     

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.     

基于启发式Q学习的汽车涂装车间作业排序优化

针对汽车涂装车间中的作业优化排序问题,提出一种基于启发式Q学习的优化算法。首先,建立包括满足总装车间生产顺序和最小化喷枪颜色切换次数的多目标整数规划模型。将涂装作业优化排序问题抽象为马尔可夫过程,建立基于启发式Q算法的求解方法。通过具体案例,对比分析了启发式Q学习、Q学习、遗传算法三种方案的优劣。结果表明：在大规模问题域中,启发式Q学习算法具有寻优效率更高、效果更好的优势。本研究为机器学习算法在汽车涂装作业优化排序问题的应用提出了新思路。     

Multicriteria order acceptance decision support in over-demanded job shops: A neural network approach

Order acceptance is an important issue in job shop production systems where demand exceeds capacity. In this paper, a neural network approach is developed for order acceptance decision support in job shops with machine and manpower capacity constraints. First, the order acceptance decision problem is formulated as a sequential multiple criteria decision problem. Then a neural network based preference model for order prioritization is described. The neural network based preference model is trained using preferential data derived from pairwise comparisons of a number of representative orders. An order acceptance decision rule based on the preference model is proposed. Finally, a numerical example is discussed to illustrate the use of the proposed neural network approach. The proposed neural network approach is shown to be a viable method for multicriteria order acceptance decision support in over-demanded job shops.     

An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective

In this paper, we propose an exact solution method for single machine scheduling problems typically arising from bottleneck-based decomposition of weighted tardiness job shops. The encountered subproblems are characterized by delayed precedence constraints, multiple local due dates per operation and an objective function that is given by a weighted sum of maximum tardiness values. The key concept for solving these subproblems to optimality is a dominance rule whose underlying concepts have been newly developed to cope with the given structural properties. Furthermore, a simple lower bound and a dedicated constraint programming technique are presented. The efficiency of the proposed method is demonstrated by means of single machine problems collected during a run of a shifting bottleneck procedure for job shops in different size and due date tightness configurations.