Complexity results and approximation algorithms for the two machine no-wait flow-shop with limited machine availability

The scheduling problems studied in this paper concern a two-machine no-wait flow shop problem with limited machine availability. In this model, we assume that machines may not always be available, for example because of preventive maintenance. We only consider the deterministic case where the unavailable periods are known in advance. The objective function considered is the maximum completion time (C_max). We prove that the problem is NP-hard even if only one non-availability period occurs on one of machines, and NP-hard in the strong sense for arbitrary numbers of non-availability periods. We also provide heuristic algorithms with error bounding analysis.     

Two-machine flowshop scheduling with availability constraints

The majority of the scheduling literature carries a common assumption that machines are available all the time. However, this availability assumption may not be true in real industry settings, since a machine may become unavailable during certain periods of time when, for instance, a machine breakdown or a preventive maintenance activity is scheduled. Although the problem is realistic and important, it is relatively new and unstudied. In this paper, we study the two-machine flowshop problem under the assumption that the unavailable time is known in advance. We assume that if a job cannot be finished before the next down period of a machine then the job will have to partially restart when the machine has become available again. We call our model semiresumable. Our model contains two important special cases: resumable where the job can be continued without any penalty and nonresumable where the job needs to totally restart. We study the problem where an availability constraint is imposed only on one machine as well as on both machines. We provide complexity analysis, develop a pseudo-polynomial dynamic programming algorithm to solve the problem optimally and also propose heuristic algorithms with an error bound analysis.     

A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint

This paper studies a two-machine open shop scheduling problem with an availability constraint, ie we assume that a machine is not always available and that the processing of the interrupted job can be resumed when the machine becomes available again. We consider the makespan minimization as criterion. This problem is NP-hard. We develop a pseudo-polynomial time dynamic programming algorithm to solve the problem optimally when the machine is not available at time s>0. Then, we propose a mixed integer linear programming formulation, that allows to solve instances with up to 500 jobs optimally in less than 5?min with CPLEX solver. Finally, we show that any heuristic algorithm has a worst-case error bound of 1.     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.     

Scatter search for minimizing weighted tardiness in a single machine scheduling with setups

Single machine scheduling problems have many real-life applications and may be hard to solve due to the particular characteristics of some production environments. In this paper, we tackle the single machine scheduling problem with sequence-dependent setup times with the objective of minimizing the weighted tardiness. To solve this problem, we propose a scatter search algorithm which uses path relinking in its core. This algorithm is enhanced with some procedures to speed-up the neighbors’ evaluation and with some diversification and intensification techniques, the latter taking some elements from iterated local search. We conducted an experimental study across a well-known set of instances to analyze the contribution of each component to the overall performance of the algorithm, as well as to compare our proposal with the state-of-the-art metaheuristics, obtaining competitive results. We also propose a new benchmark with larger and more challenging instances and provide the first results for them.     

Single-machine scheduling with maintenance and repair rate-modifying activities

Most papers in the scheduling field are based on the assumption that machines are always available at constant speed. However, in industry applications, it is very common for a machine to be in subnormal condition after running for a certain period of time. Motivated by a problem commonly found in the surface-mount technology of electronic assembly lines, this paper deals with scheduling problems involving repair and maintenance rate-modifying activities. When a machine is running at less than an efficient speed, a production planner can decide to stop the machine and maintain it or wait and maintain it later. If the choice is made to continue running the machine without fixing it, it is possible that the machine will break down and repair will be required immediately. Both maintenance and repair activities can change the machine speed from a sub-normal production rate to a normal one. Hence, we call them rate-modifying activities. Our purpose here is to simultaneously sequence jobs and schedule maintenance activity to optimize regular performance measures. In this paper, we assume that processing time is deterministic, while machine break down is a random process following certain distributions. We consider two types of processing cases: resumable and nonresumable. We study problems with objective functions such as expected makespan, total expected completion time, maximum expected lateness, and expected maximum lateness, respectively. Several interesting results are obtained, especially for the nonresumable case.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

Stochastic single machine scheduling problem as a multi-stage dynamic random decision process

In this work, we study a stochastic single machine scheduling problem in which the features of learning effect on processing times, sequence-dependent setup times, and machine configuration selection are considered simultaneously. More precisely, the machine works under a set of configurations and requires stochastic sequence-dependent setup times to switch from one configuration to another. Also, the stochastic processing time of a job is a function of its position and the machine configuration. The objective is to find the sequence of jobs and choose a configuration to process each job to minimize the makespan. We first show that the proposed problem can be formulated through two-stage and multi-stage Stochastic Programming models, which are challenging from the computational point of view. Then, by looking at the problem as a multi-stage dynamic random decision process, a new deterministic approximation-based formulation is developed. The method first derives a mixed-integer non-linear model based on the concept of accessibility to all possible and available alternatives at each stage of the decision-making process. Then, to efficiently solve the problem, a new accessibility measure is defined to convert the model into the search of a shortest path throughout the stages. Extensive computational experiments are carried out on various sets of instances. We discuss and compare the results found by the resolution of plain stochastic models with those obtained by the deterministic approximation approach. Our approximation shows excellent performances both in terms of solution accuracy and computational time.

     

Uniform machine scheduling with machine available constraints

1.IntroductionIntheclassicalparallelmachineschedulingareaweassumethatmachinesarealwaysavailable.However,aspointedin[1],inrealindustrysettingsthisassumptionmaynotbetrue.Forexample,machinesmaynotalwaysbeavailablebecauseoftheirpreventivemaintenanceduringtheschedulingperiod.Thatistosay,eachmachineiisunavailablefromsibuntilrib(05sib5rib),where0SkSm,withmbeingthenumberofunavailabilityperiodsformachineiduringtheplanninghorizon.Inotherwords,somepapersstatethatmachinesareavailableintimewindows,whichi…     

Fast and effective algorithms for the liquid crystal display module (LCM) scheduling problem with sequence-dependent setup time

The liquid crystal display module scheduling problem (LCMSP) is a variation of the classical parallel machines scheduling problem, which has many real-world applications, particular, in the thin film transistor liquid crystal display (TFT-LCD) manufacturing industry. In this paper, we present a case study on the LCMSP, which is taken from a final liquid crystal display module (LCM) shop floor in a TFT-LCD industry. For the case we investigated, the jobs are clustered by their product types and the machine setup time is sequentially dependent on the product types of the jobs processed on the machine. In LCMSP, the objective is to maximize the total profit subject to fulfilling contracted quantities without violating the due date and machine capacity restrictions. The LCMSP can be modelled as a multi-level optimization problem. The sub-problem of LCMSP can be transformed into the vehicle routing problem with time window (VRPTW). One can therefore solve the LCMSP efficiently using existing VRPTW algorithms. We present two new algorithms based on the savings algorithms with some modifications to accommodate the LCMSP. Based on the characteristics of the LCM process, a set of test problems is generated covering most of the real-world applications for test purposes. Computational results and performance comparisons show that the proposed algorithms solved the LCMSP efficiently and near-optimally.     

Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time

We are interested in the problem of scheduling orders for different product types in a facility with a number of machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover, when a machine in this case switches over from one product type to another, no setup is required. Each order has a release date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders. Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments. We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights into the trade-offs with regard to solution quality, speed, and memory space. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This research is supported by the National Science Foundation through grants DMI-0300156 and DMI-0245603.     

Application of an optimization problem in Max-Plus algebra to scheduling problems

The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2×2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3×3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed.     

A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.     

Capacity planning by the dynamic multi-resource generalized assignment problem (DMRGAP)

The allocation of available capacity among competing demand and users is a problem encountered in areas such as job shop scheduling, the trucking industry and distributed computer systems. In all these areas a model known as the Multi-Resource Generalized Assignment Problem (MRGAP) has been proposed as a tool to assign available capacity among the competing applications. In this paper we extend the MRGAP model to the case where demand varies over time and capacity assignments are dynamic. We show that the extended model can be used for strategic capacity planning and we develop efficient solution procedures to solve the dynamic version of MRGAP.     

Large deviations analysis of the generalized processor sharing policy

In this paper we consider a stochastic server (modeling a multiclass communication switch) fed by a set of parallel buffers. The dynamics of the system evolve in discrete-time and the generalized processor sharing (GPS) scheduling policy of [25] is implemented. The arrival process in each buffer is an arbitrary, and possibly autocorrelated, stochastic process. We obtain a large deviations asymptotic for the buffer overflow probability at each buffer. In the standard large deviations methodology, we provide a lower and a matching (up to first degree in the exponent) upper bound on the buffer overflow probabilities. We view the problem of finding a most likely sample path that leads to an overflow as an optimal control problem. Using ideas from convex optimization we analytically solve the control problem to obtain both the asymptotic exponent of the overflow probability and a characterization of most likely modes of overflow. These results have important implications for traffic management of high-speed networks. They extend the deterministic, worst-case analysis of [25] to the case where a detailed statistical model of the input traffic is available and can be used as a basis for an admission control mechanism. This revised version was published online in June 2006 with corrections to the Cover Date.     

Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.     

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.     

The wafer probing scheduling problem (WPSP)

The wafer probing scheduling problem (WPSP) is a variation of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the integrated circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. Further, the job processing time depends on the product type, and the machine setup time is sequence dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequence dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we formulate the WPSP as an integer programming problem. We also transform the WPSP into the vehicle routing problem with time windows (VRPTW), a well-known network routing problem which has been investigated extensively. An illustrative example is given to demonstrate the proposed transformation. Based on the provided transformation, we present three efficient algorithms to solve the WPSP near-optimally.     

Minimizing makespan for two parallel machines with job limit on each availability interval

We consider the problem of scheduling jobs on two parallel machines that are not continuously available for processing. The machine is not available after processing a fixed number of jobs in order to make precision adjustment of machines such as in wafer manufacturing, to reload the feeder in printed circuit board production, or to undertake any other maintenance works such as cleaning and safety inspections. The objective of the problem is to minimize the makespan. Two different scheduling horizons are investigated for this problem. For the short-term scheduling horizon, we consider only the time period before the unavailability interval, while for the long-term horizon, machines are allowed to restart processing after the unavailability interval. For both cases, which are strongly NP-hard, exact optimization algorithms based on the branch and bound method are proposed. Although the algorithms have exponential time complexities, computational results show that they can solve optimally the various-sized problems in reasonable computation time.     

A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates

In most deterministic scheduling problems, job-processing times are regarded as constant and known in advance. However, in many realistic environments, job-processing times can be controlled by the allocation of a common resource to jobs. In this paper, we consider the problem of scheduling jobs with arbitrary release dates and due dates on a single machine, where job-processing times are controllable and are modeled by a non-linear convex resource consumption function. The objective is to determine simultaneously an optimal processing permutation as well as an optimal resource allocation, such that no job is completed later than its due date, and the total resource consumption is minimized. The problem is strongly NP\mathcal{NP}-hard. A branch and bound algorithm is presented to solve the problem. The computational experiments show that the algorithm can provide optimal solution for small-sized problems, and near-optimal solution for medium-sized problems in acceptable computing time.