Scheduling an unbounded batching machine with family jobs and setup times

We consider the problem of scheduling n jobs on an unbounded batching machine that can process any number of jobs belonging to the same family simultaneously in the same batch. All jobs in the same batch complete at the same time. Jobs belonging to different families cannot be processed in the same batch, and setup times are required to switch between batches that process jobs from different families. For a fixed number of families m, we present a generic forward dynamic programming algorithm that solves the problem of minimizing an arbitrary regular cost function in pseudopolynomial time. We also present a polynomial-time backward dynamic programming algorithm with time complexity O (mn(n/m+1) ^m ) for minimizing any additive regular minsum objective function and any incremental regular minmax objective function. The effectiveness of our dynamic programming algorithm is shown by computational experiments based on the scheduling of the heat-treating process in a steel manufacturing plant.     

A note on scheduling jobs with equal processing times and inclusive processing set restrictions

We consider the problem of scheduling n jobs on m parallel machines with inclusive processing set restrictions. Each job has a given release date, and all jobs have equal processing times. The objective is to minimize the makespan of the schedule. Li and Li (2015) have developed an O(n²+mn log?n) time algorithm for this problem. In this note, we present a modified algorithm with an improved time complexity of O(min{m, log?n} ? n log?n).     

A note on parallel-machine due-window assignment

We consider a due-window assignment problem on identical parallel machines, where the jobs have equal processing times and job-dependent earliness-tardiness costs. We would like to determine a ‘due window’ during which the jobs can be completed at no cost and to obtain a job schedule in which the jobs are penalized if they finish before or after the due window. The objective is to minimize the total earliness and tardiness job penalty, plus the cost associated with the size of the due window. We present an algorithm that can solve this problem in O(n³) time, which is an improvement of the O(n⁴) solution procedure developed by Mosheiov and Sarig.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

The equal allocation policy in open shop batch scheduling

We study the optimality of the very practical policy of equal allocation of jobs to batches in batch scheduling problems on an m-machine open shop. The objective is minimum makespan. We assume unit processing time jobs, machine-dependent setup times and batch availability. We show that equal allocation is optimal for a two-machine and a three-machine open shop. Although, this policy is not necessarily optimal for larger size open shops, it is shown numerically to produce very close-to-optimal schedules.     

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.     

Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.     

Minimizing the number of early jobs on a proportionate flowshop

A proportionate flowshop is a special case of the classical flowshop, where the job processing times are machine-independent. We study the problem of minimizing the number of early jobs in this machine setting. This objective function has hardly been investigated on a single machine, and never on a flowshop. We introduce an efficient iterative solution algorithm. In each iteration, a single job is moved to the first position (and is added to the set of early jobs), and the remaining jobs are rescheduled such that the maximum earliness is minimized. The algorithm guarantees an optimal solution in O(n³) time, where n is the number of jobs.     

Solution of the NP-hard total tardiness minimization problem in scheduling theory

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT _j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n ²Σp _j ), where n is the number of jobs and p _j is the processing time of the jth job (j = 1, 2, …, n).     

Three-machine shop scheduling with partially ordered processing routes

This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M₁,M₂ and M_{3}. A job is first processed on M₁ and then is assigned either the route (M₂,M_{3}) or the route (M_{3},M₂). Thus, for our model the processing route is given by a partial order of machines, as opposed to the linear order of machines for a job shop, or to an arbitrary sequence of machines for an open shop. The main result is on O(nlog n) time heuristic, which generates a schedule with the makespan that is at most 5/3 times the optimum value.     

Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence

This paper discusses a two-stage assembly-type flowshop scheduling problem with batching considerations subject to a fixed job sequence. The two-stage assembly flowshop consists of m stage-1 parallel dedicated machines and a stage-2 assembly machine which processes the jobs in batches. Four regular performance metrics, namely, the total completion time, maximum lateness, total tardiness, and number of tardy jobs, are considered. The goal is to obtain an optimal batching decision for the predetermined job sequence at stage 2. This study presents a two-phase algorithm, which is developed by coupling a problem-transformation procedure with a dynamic program. The running time of the proposed algorithm is O(mn+n⁵), where n is the number of jobs.     

Balancing Workloads and Minimizing Set-up Costs in the Parallel Processing Shop

This paper presents an optimal scheduling algorithm for minimizing set-up costs in the parallel processing shop while meeting workload balancing restrictions.There are M independent batch type jobs which have sequence dependent set-up costs and N parallel processing machines. Each of the M jobs must be processed on exactly one of the N available machines. It is desirable to minimize total changeover costs with the restriction that each machine workload assignment T _n be within P units of the average machine assignment. The paper describes a static problem in which all jobs are available at time zero. The sequence dependent change over costs are identical for each machine. An extension of the algorithm handles nonidentical processor problems.A combinatorial programming approach to the problem is used. For the special case of identical processors, the problem can be treated as a multi-salesman travelling salesman problem. A general branch and bound algorithm and numerical results are given.     

Two-stage flexible flow shop scheduling subject to fixed job sequences

This paper investigates the scheduling problem in a two-stage flexible flow shop, which consists of m stage-1 parallel dedicated machines and a stage-2 bottleneck machine, subject to the condition that n _l jobs per type l∈{1, …, m} are processed in a fixed sequence. Four regular performance metrics, including the total completion time, the maximum lateness, the total tardiness, and the number of tardy jobs, are considered. For each considered objective function, we aim to determine an optimal interleaving processing sequence of all jobs coupled with their starting times on the stage-2 bottleneck machine. The problem under study is proved to be strongly NP-hard. An O(m²Π_l=1 ^m n _l ²) dynamic programming algorithm coupled with numerical experiments is presented.     

Optimal Due-Date Determination and Sequencing of <Emphasis Type="Italic">n</Emphasis> Jobs on a Single Machine

Given a set of n jobs with deterministic processing times and the same ready times, the problem is to find the optimal processing-time multiple k* for the T.W.K. due-date assignment method, and the optimal sequence σ* to minimize the total amount of missed due-dates. It is found that k* is a constant for a given job set and σ* should be in S.P.T. sequence. After the theoretical treatment, a numerical example is given for discussion. The optimal results can readily be extended to situations in which the processing times are random variables with known means and having the same coefficient of variation. From a practical point of view, the main merit of this paper is that it demonstrates how, under certain production environments in which completion times of the jobs can be anticipated, to determine the optimal due-dates and obtain the optimal sequence.     

Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.     

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.     

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.     

Due-date assignment and single machine scheduling with deteriorating jobs

We study a scheduling problem with deteriorating jobs, that is, jobs whose processing times are an increasing function of their start times. We consider the case of a single machine and linear job-independent deterioration. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of due-date, earliness and tardiness penalties. We give an O(n log n) time algorithm to solve this problem.     

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 sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize the sum of maximum earliness and maximum tardiness when sequence-dependent setup times exist (1∣ST _sd ∣ET_max). In this paper, an optimal branch-and-bound algorithm is developed that involves the implementation of lower and upper bounding procedures as well as three dominance rules. For solving problems containing large numbers of jobs, a polynomial time-bounded heuristic algorithm is also proposed. Computational experiments demonstrate the effectiveness of the bounding and dominance rules in achieving optimal solutions in more than 97% of the instances.