Scheduling a variable maintenance and linear deteriorating jobs on a single machine

We investigate a single machine scheduling problem in which the processing time of a job is a linear function of its starting time and a variable maintenance on the machine must be performed prior to a given deadline. The goals are to minimize the makespan and the total completion time. We prove that both problems are NP-hard. Furthermore, we show that there exists a fully polynomial time approximation scheme for the makespan minimization problem. For the total completion time minimization problem we point out that there exists a fully polynomial time approximation scheme for a special case.     

Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine

The scheduling problem with deteriorating jobs to minimize the makespan on a single machine where the facility has an availability constraint is studied in this paper. By a deteriorating job we mean that the processing time for the job is a function of its starting time. Even with the introduction of the availability to a facility, the linear deteriorating model can be solved using the 0-1 integer programming technique if the actual job processing time is proportional to the starting time.     

Scheduling resumable simple linear deteriorating jobs on a single machine with an availability constraint to minimize makespan

We consider a single-machine scheduling problem in which the processing time of each job is a simple linear deteriorating function of its waiting time. The machine is subject to an availability constraint. Jobs interrupted by machine unavailability can resume their processing. The objective is to minimize the makespan. We first show that the problem can be solved optimally by 0–1 integer programming. We then prove that the problem is NP-hard in the ordinary sense and there exists a fully polynomial time approximation scheme for it.     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.     

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

This paper considers single machine scheduling problems with setup times and deteriorating jobs. The setup times are proportional to the length of the already processed jobs, that is, the setup times are past-sequence-dependent (p-s-d). It is assumed that the job processing times are defined by functions dependent on their starting times. The following objectives are considered: the makespan, the total completion time, and the sum of earliness, tardiness, and due-window starting time and size penalties. We propose polynomial time algorithms to solve these problems.     

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

This paper considers single machine scheduling problems with setup times and deteriorating jobs. The setup times are proportional to the length of the already processed jobs, that is, the setup times are past-sequence-dependent (p-s-d). It is assumed that the job processing times are defined by functions dependent on their starting times. The following objectives are considered: the makespan, the total completion time, and the sum of earliness, tardiness, and due-window starting time and size penalties. We propose polynomial time algorithms to solve these problems.     

Scheduling grouped jobs on single machine with genetic algorithm

Production scheduling of grouped jobs has been an active research area since GT (Group Technology) was widely applied in practical manufacturing systems. To minimize the total flowtime of grouped jobs on a single machine, we combine jobs into fundamental runs based upon the necessary condition of the optimal solution. It is proved that the optimal solution is a combination of fundamental runs. A genetic algorithm is designed based on studies on the combinatorial rules of fundamental runs. The numerical results show that the computational performance of the algorithm depends on the number of ‘fundamental’ runs, not on the number of jobs. In general, the number of fundamental runs is far less than the number of jobs. Therefore, the algorithm has potential for practical application in large scale production systems.     

Scheduling problems with deteriorating jobs and learning effects including proportional setup times

Recently, interest in scheduling with deteriorating jobs and learning effects has kept growing. However, research in this area has seldom considered setup times. We introduce a new scheduling model in which job deterioration and learning, and setup times are considered simultaneously. In the proposed model, the actual processing time of a job is defined as a function of the setup and processing times of the jobs already processed and the job’s own scheduled position in a sequence. In addition, the setup times are assumed to be proportional to the actual processing times of the already scheduled jobs. We derive polynomial-time optimal solutions for some single-machine problems with or without the presence of certain conditions.     

Scheduling jobs on a single machine to maximize the total revenue of jobs

In today's hyper-competitive marketplace, many products like memory chips and computers are characterized by short life cycles and rapidly declining sales prices. This implies that the amount of revenue generated as a result of completing a product (job) may be decreasing as its completion time is delayed. In such an environment, there is a decided preference for the maximization of product revenues as an important objective. Based on the assumption that the decreasing rate of revenue is dependent on their product types, we intend to develop a searching algorithm and some heuristic algorithms to locate optimal and near-optimal job sequences, respectively, and thereby maximize total earned revenue.     

Scheduling linearly deteriorating jobs on multiple machines

This paper investigates the scheduling problems in which the job processing times do not remain constant but are increasing linear functions of their starting times. Two deteriorating scheduling models, Model 1 and Model 2, for multiple machines are considered, with the goal being to minimize the makespan. In this paper, we propose an efficient heuristic for Model 1 and prove that the ratio of the makespan obtained by the heuristic to the optimal makespan is bounded. For Model 2, three heuristics, including a probabilistic heuristic, are proposed for minimizing the makespan. Numerical results are provided to show the efficiency of the approaches in this paper.     

Scheduling jobs with equal processing times subject to machine eligibility constraints

We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.     

Scheduling a single machine with concurrent jobs for the frozen food industry

This study examines the air blast freezing process of the frozen food industry, which processes multiple products with variable processing rates. The analysis depicts a new, single machine-scheduling problem in which the machine can process multiple jobs concurrently, within its capacity. The machine processes independent jobs arriving at various times while incurring interruption costs when allowing the jobs to enter or leave the machine. A mixed integer linear programming (MILP) model and a heuristic algorithm are developed for scheduling, the objectives of which are to minimize the costs associated with machine activities including that of waiting to load, waiting to unload and interruption time. The heuristic algorithm demonstrates the high potential of the computational time savings by obtaining the solution within one-fifth of the mathematical model computational time.     

On scheduling a single machine with resource dependent release times

We consider a single machine scheduling problem with resource dependent release times that can be controlled by a non-increasing convex resource consumption function. The objective is to minimize the weighted total resource consumption and sum of job completion times with an initial release time greater than the total processing times. It is known that the problem is polynomially solvable in O(n⁴) with n the number of jobs.     

A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity

This note considers a single machine scheduling and due-window assignment problem, in which the processing time of a job is a linear function of its starting time and the job-independent deterioration rates are identical for all jobs. We allow an option for performing a rate-modifying activity for changing the normal processing times of the jobs following this activity. The objective is to schedule the jobs, the due-window and the rate-modifying activity so as to minimize the sum of earliness, tardiness and due-window starting time and due-window size costs. We introduce a polynomial solution for the problem.     

Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective

In this paper, we minimize the weighted and unweighted number of tardy jobs on a single batch processing machine with incompatible job families. We propose two different mixed integer linear programming (MILP) formulations based on positional variables. The second formulation does not contain a big-M coefficient. Two iterative schemes are discussed that are able to provide tighter linear programming bounds by reducing the number of positional variables. Furthermore, we also suggest a random key genetic algorithm (RKGA) to solve this scheduling problem. Results of computational experiments are shown. The second MILP formulation is more efficient with respect to lower bounds, while the first formulation provides better upper bounds. The iterative scheme is effective for the weighted case. The RKGA is able to find high-quality solutions in a reasonable amount of time.     

Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times

We study the problem of maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times. Unlike the vast majority of the literature, we do not restrict ourselves to a specific model of processing time function. Rather, we assume that the processing time function can be of any functional structure that is according to one of the following two cases. The first is the case where the job processing times are under a learning effect, i.e., each job processing time is a non-increasing function of its position in the sequence. In the second case, an aging effect is assumed, i.e., each job processing time is a non-decreasing function of its position in the sequence. We prove that the problem is strongly $\mathcal{N }\mathcal{P }$ N P -hard under a learning effect, even if all the weights are identical. When there is an aging effect, we introduce a dynamic programming (DP) procedure that solves the problem with arbitrary weights in $O(n^{3})$ O ( n 3 ) time (where $n$ n is the number of jobs). For identical weights, a faster optimization algorithm that runs in $O(n\log n)$ O ( n log n ) time is presented. We also extend the analysis to the case of scheduling on a set of $m$ m parallel unrelated machines and provide a DP procedure that solves the problem in polynomial time, given that $m$ m is fixed and that the jobs are under an aging effect.     

Scheduling jobs on a single serial-batching machine with dynamic job arrivals and multiple job types

This paper investigates a scheduling model with certain co-existing features of serial-batching, dynamic job arrival, multi-types of job, and setup time. In this proposed model, the jobs of all types are first partitioned into serial batches, which are then processed on a single serial-batching machine with an independent constant setup time for each new batch. In order to solve this scheduling problem, we divide it into two phases based on job arrival times, and we also derive and prove certain constructive properties for these two phases. Relying on these properties, we develop a two-phase hybrid algorithm (TPHA). In addition, a valid lower bound of the problem is also derived. This is used to validate the quality of the proposed algorithm. Computational experiments, both with small- and large-scale problems, are performed in order to evaluate the performance of TPHA. The computational results indicate that TPHA outperforms seven other heuristic algorithms. For all test problems of different job sizes, the average gap percentage between the makespan, obtained using TPHA, and the lower bound does not exceed 5.41 %.     

Scheduling jobs on parallel machines with setup times and ready times

In this research we are interested in scheduling jobs with ready times on identical parallel machines with sequence dependent setups. Our objective is to minimize the total weighted tardiness. As this problem is NP-Hard, we develop a heuristic to solve this problem in reasonable time. Our approach is an extension of the apparent tardiness cost with setups (ATCS) approach by [Lee, Y. H., Pinedo, M. (1997). Scheduling jobs on parallel machines with sequence dependent setup times. European Journal of Operational Research, 100, 464–474.] to allow non-ready jobs to be scheduled – meaning we allow a machine to remain idle for a high priority job arriving at a later time. To determine the scaling parameters for our composite dispatching rule (called ATCSR), we first develop a ‘grid approach’ that considers multiple values for the scaling parameters, generates multiple schedules, and chooses the best schedule for the solution. This experimentation was then used to develop regression equations to predict the values of the scaling parameters that would yield the highest quality solution. The grid and regression versions of ATCSR provide better performance than grid and empirically based formula versions of ATCS, BATCS, and X-RM which are the prominent algorithms in the literature.