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.     

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

Backtracking and its Amoebic Properties in One-dimensional Machine Location Problems

This paper studies the assignment of M unique machines to M equally spaced locations along a linear material handling track with the objective of minimizing the cost of (jobs) backtracking (i.e. moving upstream). Because of the arrangement of machines and restrictions imposed by the sequence of operations for each job, some jobs may have to backtrack to complete required processing on different machines. This problem is formulated as a quadratic assignment problem. An optimal solution to a problem with large M is computationally intractable. The backtracking distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Ten amoebic properties have been identified and exploited to devise a heuristic and a lower bound on the optimal solution. Results which describe the performance of the heuristic and the lower bound are presented.     

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.     

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.     

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.     

Single machine scheduling with time deteriorating job values

This paper considers the problem of scheduling n jobs on a single machine where the job value deteriorates with its starting time. The objective of the problem is to maximize the cumulative value of all jobs. The problem is motivated from the real-life applications, such as movie scheduling, remanufacturing of high-technology products, web object transmission, and banner advertising. Unrestricted, truncated, and capacity constrained job value functions are considered. Some special cases of the problem, such as the unrestricted linear job value function, are polynomially solvable. The general problem is shown to be unary NP-hard and is modelled as a time index integer program. For the NP-hard cases, several heuristics are proposed. Results of the empirical evaluation of the relative performance of the proposed heuristics on critical parameters are reported.     

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).     

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.     

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.     

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.     

Minimizing the Flow-time Variance in Single-machine Systems

In this paper we deal with an n-job, single-machine scheduling problem. All jobs are available from the start, and the objective is to minimize the variance of job flow-times. A heuristic procedure which is based on the complementary pair-exchange principle is proposed. It has been concluded that this heuristic procedure provides improved results (in terms of objective-function value) when compared with other heuristics. Our heuristic procedure has the complexity of O(n log 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.     

Λ-Shaped Policies to Schedule Deteriorating Jobs

We study a problem of scheduling deteriorating jobs, i.e. jobs whose processing times are an increasing function of their starting times. We consider the case of a single machine and linear job-independent deterioration. The objective is to minimize the sum of weighted completion times, with weights proportional to the basic processing times. The optimal schedule is shown to be Λ-shaped, i.e. the sequence of the basic processing times has a single local maximum. Moreover, we show that the problem is solved in O(N log N) time. In the last section we test heuristics for the case of general weights.     

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.     

Minimizing makespan in re-entrant permutation flow-shops

A re-entrant flow-shop (RFS) describes situations in which every job must be processed on machines in the order of M₁, M₂, …, M _m , M₁, M₂, …,M _m , …, and M₁, M₂, …,M _m . In this case, every job can be decomposed into L levels and each level starts on M₁, and finishes on M _m . In a RFS case, if the job ordering is the same on any machine at each level, then it is said that no passing is allowed since any job is not allowed to pass any previous job. The RFS scheduling problem where no passing is allowed is called the re-entrant permutation flow-shop (RPFS) problem. This paper proposes three extended mixed BIP formulations and six extended effective heuristics for solving RPFS scheduling problems to minimize makespan.     

An Improved Solution Procedure for the Scheduling Problem

Given a set of n jobs to be processed on a single machine, the problem is to find an optimal job sequence that hierarchically minimizes a bi-criterion objective function. The primary criterion is the maximum value of a general non-decreasing penalty function of job completion time, while the secondary criterion is total job flow time. An extension of Emmons's result is presented on the basis of which an improved solution procedue is developed to reduce the computational effort to find the optimal solution.     

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.     

Vector scheduling with rejection on a single machine

In this paper, we study a vector scheduling problem with rejection on a single machine, in which each job is characterized by a d-dimension vector and a penalty, in the sense that, jobs can be either rejected by paying a certain penalty or assigned to the machine. The objective is to minimize the sum of the maximum load over all dimensions of the total vector of all accepted jobs, and the total penalty of rejected jobs. We prove that the problem is NP-hard and design two approximation algorithms running in polynomial time. When d is a fixed constant, we present a fully polynomial time approximation scheme.     

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.