Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance

This paper deals with a single machine scheduling problems with availability constraints. The unavailability of machine results from periodic maintenance activities. In our research, a periodic maintenance consists of several maintenance periods. We consider a machine should stop to maintain after a periodic time interval or to change tools after a fixed amount of jobs processed simultaneously. Each maintenance period is scheduled after a periodic time interval. We study the problems under deterministic environment and flexible maintenance considerations. Preemptive operation is not allowed. In addition, we propose a more reasonable flexible model for the real production settings. The objective is to minimize the makespan. The proposed problem is NP-hard in the strong sense and some heuristic algorithms are provided. The purpose is to present an efficient and effective heuristic algorithm so that it will be straightforward and easy to implement. Computational results show that the proposed algorithm first fit decreasing (DFF) performs well.     

Minimizing total flow time in the single-machine scheduling problem with periodic maintenance

This paper deals with a single-machine scheduling problem with limited machine availability. The limited availability of machine results from periodic maintenance activities. In our research, a periodic maintenance schedule consists of several maintenance periods. Each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the total flow time subject to periodic maintenance and nonresumable jobs. Some important theorems are proved for the problem. A branch-and-bound algorithm that utilizes several theorems is proposed to find the optimal schedule. We also develop a heuristic to solve large sized problems. In this paper, computational results show that the proposed heuristic is highly accurate and efficient.     

Single-machine scheduling problems with past-sequence-dependent setup times

This paper studies single-machine scheduling problems with setup times which are proportionate to the length of the already scheduled jobs, that is, with past-sequence-dependent or p-s-d setup times. The following objective functions are considered: the maximum completion time (makespan), the total completion time, the total absolute differences in completion times and a bicriteria combination of the last two objective functions. It is shown that the standard single-machine scheduling problem with p-s-d setup times and any of the above objective functions can be solved in O(nlog n) time (where n is the number of jobs) by a sorting procedure. It is also shown that all of our results extend to a “learning” environment in which the p-s-d setup times are no longer linear functions of the already elapsed processing time due to learning effects.     

A due-window assignment problem with position-dependent processing times

We extend a classical single-machine due-window assignment problem to the case of position-dependent processing times. In addition to the standard job scheduling decisions, one has to assign a time interval (due-window), such that jobs completed within this interval are assumed to be on time and not penalized. The cost components are: total earliness, total tardiness and due-window location and size. We introduce an O(n³) solution algorithm, where n is the number of jobs. We also investigate several special cases, and examine numerically the sensitivity of the solution (schedule and due-window) to the different cost parameters.     

Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times

In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier – this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

Minimizing weighted earliness–tardiness and due-date cost with unit processing-time jobs

The classical single-machine scheduling and due-date assignment problem of Panwalker et al. [Panwalker, S.S., Smith, M.L., Seidmann, A., 1982. Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research 30(2) (1982) 391–399] is the following: All n jobs share a common due-date, which is to be determined. Jobs completed prior to or after the due-date are penalized according to a cost function which is linear and job-independent. The objective is to minimize the total earliness–tardiness and due-date cost. We study a generalized version of this problem in which: (i) the earliness and tardiness costs are allowed to be job dependent and asymmetric and (ii) jobs are processed on parallel identical machines. We focus on the case of unit processing-time jobs. The problem is shown to be solved in polynomial (O(n⁴)) time. Then we study the special case with no due-date cost (a classical problem known in the literature as TWET). We introduce an O(n³) solution for this case. Finally, we study the minmax version of the problem, (i.e., the objective is to minimize the largest cost incurred by any of the jobs), which is shown to be solved in polynomial time as well.     

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.     

An exact algorithm for the bi-objective timing problem

The timing problem in the bi-objective just-in-time single-machine job-shop scheduling problem (JiT-JSP) is the task to schedule N jobs whose order is fixed, with each job incurring a linear earliness penalty for finishing ahead of its due date and a linear tardiness penalty for finishing after its due date. The goal is to minimize the earliness and tardiness simultaneously. We propose an exact greedy algorithm that finds the entire Pareto front in \(O(N^2)\) time. This algorithm is asymptotically optimal.     

Single-machine scheduling with logarithm deterioration

Traditionally, job processing times are assumed to be known and fixed; however, there are many situations in which a job that is processed later consumes more time than the same job when it is processed earlier. This is known as deteriorating jobs scheduling in the literature. Most of the research in deteriorating jobs scheduling assumes that the actual job processing time is a linear function of its starting time. Thus, the actual job processing times might increase significantly if the number of jobs or the job sizes increase. Motivated by this limitation, this paper addresses a new deterioration model where the actual job processing time is a function of the logarithm of the job processing times already processed. Under the proposed model, we provide the optimal solutions for some single-machine problems.     

Scheduling with target start times

We address the single-machine problem of scheduling n independent jobs subject to target start times. Target start times are essentially release times that may be violated at a certain cost. The objective is to minimize a bicriteria objective function that is composed of total completion time and maximum promptness, which measures the observance of these target start times. We show that in case of a linear objective function the problem is solvable in O(n⁴) time if preemption is allowed or if total completion time outweighs maximum promptness.     

Fixed point properties of semigroups of non-expansive mappings

In recent years, there have been considerable interests in the study of when a closed convex subset K of a Banach space has the fixed point property, i.e. whenever T is a non-expansive mapping from K into K, then K contains a fixed point for T. In this paper we shall study fixed point properties of semigroups of non-expansive mappings on weakly compact convex subsets of a Banach space (or, more generally, a locally convex space). By considering the classes of bicyclic semigroups we answer two open questions, one posted earlier by the first author in 1976 (Dalhousie) and the other posted by T. Mitchell in 1984 (Virginia). We also provide a characterization for the existence of a left invariant mean on the space of weakly almost periodic functions on separable semitopological semigroups in terms of fixed point property for non-expansive mappings related to another open problem raised by the first author in 1976.     

Several single-machine scheduling problems with general learning effects

In this paper we consider several single-machine scheduling problems with general learning effects. By general learning effects, we mean that the processing time of a job depends not only on its scheduled position, but also on the total normal processing time of the jobs already processed. We show that the scheduling problems of minimization of the makespan, the total completion time and the sum of the θ  th (θ?0$\theta ?0$) power of job completion times can be solved in polynomial time under the proposed models. We also prove that some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time.     

Parallel-machine scheduling with release dates and rejection

In this paper, we consider the parallel-machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. When m is a fixed constant, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for the problem. When m is arbitrary, we present a 2-approximation algorithm for the problem.     

On A Scheduling Problem of Time Deteriorating Jobs

We consider a scheduling problem with a single machine and a set of jobs which have to be processed sequentially. While waiting for processing, jobs may deteriorate, causing the processing requirement of each job to grow after a fixed waiting timet₀. We prove that the problem of minimizing the makespan—completion time for all jobs—is NP-hard. Next we consider the problem for a natural special case where the job requirement grows linearly at a job-specific rate aftert₀. We develop a fully polynomial time approximation scheme for the problem in this case. We also give further NP-hardness results, and a polynomial time algorithm for the case where the job-specific rate is proportional to the initial processing requirement of each job.     

Batch scheduling with controllable setup and processing times to minimize total completion time

We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n³ log n) and O(n⁵) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.     

Two-stage open shop scheduling with a bottleneck machine

It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P≠NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m⩾2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4.     

Single-machine scheduling with common due-window assignment for deteriorating jobs

In this paper, we consider a single-machine common due-window assignment scheduling problem with deteriorating jobs. Jobs’ processing times are defined by function of their starting times and job-dependent deterioration rates that are related to jobs and are not all equal. The objective is to determine an optimal combination of sequence and common due-window location so as to minimize the weighted sum of earliness, tardiness and due-window location penalties. We propose an O(n² log n) time algorithm to solve the problem and discuss several instances to illustrate it.     

Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains

In this paper, an integrated due date assignment and production and batch delivery scheduling problem for make-to-order production system and multiple customers is addressed. Consider a supply chain scheduling problem in which n orders (jobs) have to be scheduled on a single machine and delivered to K customers or to other machines for further processing in batches. A common due date is assigned to all the jobs of each customer and the number of jobs in delivery batches is constrained by the batch size. The objective is to minimize the sum of the total weighted number of tardy jobs, the total due date assignment costs and the total batch delivery costs. The problem is NP-hard. We formulate the problem as an Integer Programming (IP) model. Also, in this paper, a Heuristic Algorithm (HA) and a Branch and Bound (B&B) method for solving this problem are presented. Computational tests are used to demonstrate the efficiency of the developed methods.     

A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity

The scheduling of maintenance activities has been extensively studied, with most studies focusing on single-machine problems. In real-world applications, however, multiple machines or assembly lines process numerous jobs simultaneously. In this paper, we study a parallel-machine scheduling problem in which the objective is to minimize the total tardiness given that there is a maintenance activity on each machine. We develop a branch-and-bound algorithm to solve the problem with a small problem size. In addition, we propose a hybrid genetic algorithm to obtain the approximate solutions when the number of jobs is large. The performance of the proposed algorithms is evaluated based mainly on computational results.