Search

In this paper, the two-machine no-wait proportionate flow shop problem is analysed with the objective of minimising the total absolute deviation of job completion times. The optimality of V-shaped ...

Anomalies in flow shop scheduling are rare; only two anomalies have been reported. We present five new anomalies for the permutation flow shop models with the minimum makespan objective and seven more anomalies for the minimum total flow time objective. These anomalies (including the existing ones) are divided into three types corresponding to an increased processing time of a single operation, the addition of a job and the addition of a machine. We derive two properties which, when satisfied, eliminate the possibility of certain anomalies. We conclude that restrictions such as no-delay schedules, no job waiting or no machine idle time (after it starts processing) often result in anomalies. We also show that anomalies can also occur in non-permutation flow shops (four new anomalies presented).

We show by induction that the shortest processing time sequence is optimal for a number of three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines, effectively proving the optimality of an index priority rule when the adjacent job pairwise interchange argument does not hold. We also show that when the middle machine is maximal, the synchronous flow, blocking and no-wait problems are equivalent, because they can be effectively decomposed into two equivalent two-stage problems. A similar equivalence is shown for the classical flow shop and the flow shop with no-idle machines. These equivalences facilitate the solution of one problem by using the optimal algorithm for the equivalent problem. Finally, we observe that when the middle machine is minimal, the optimal sequence is not a pyramid sequence for the synchronous flow and blocking flow shops. On the other hand, we show that the optimal sequence for the flow shop with no-idle machines is a pyramid sequence obtainable by dynamic programming in pseudo-polynomial time.

The schematic representation of schedules has been a useful tool for researchers; in this paper, we review existing network-based schematics for flow shop models. We also propose new schematics for flow shops with blocking, synchronous transfers, no-wait processing, no-idle time and limited buffer space. Using schematics, we explain some of the past findings and present new results. We also explain flow shop anomalies/paradoxes. Finally, we propose schematics for four flow shop models using the concept of string analog.

We analyze the ‘no-wait’ proportionate two-stage super shop scheduling problem with the objective of minimising the maximum job completion time (makespan). The existing simple sorting procedures fo...

We derive an index priority rule for an m-machine no-wait flow shop with the minimum makespan objective and specially-structured job processing times. Our rule generalizes the previously known rules for two special cases of the problem. We also derive an index priority rule for a two-machine no-wait flow shop with the minimum weighted total job completion time objective when all jobs have the same processing time on the first machine. We then show that additional index priority rules can be derived for the latter problem with other scheduling objectives. Finally, we discuss extensions to flow shops with blocking and no-wait job shops and open shops.

We derive sufficient conditions which, when satisfied, guarantee that an optimal solution for a single-machine scheduling problem is also optimal for the corresponding proportionate flow shop scheduling problem. We then utilize these sufficient conditions to show the solvability in polynomial time of numerous proportionate flow shop scheduling problems with fixed job processing times, position-dependent job processing times, controllable job processing times, and also problems with job rejection. © 2015 Wiley Periodicals, Inc. Naval Research Logistics, 2015

It is generally recognized that the first model involving job scheduling was presented by Selmer Johnson and published in the inaugural issue of Naval Research Logistics Quarterly (NRLQ) in 1954. NRLQ also published another seminal scheduling paper by Wayne E. Smith a short time later. In the present paper, we discuss the contribution of NRLQ and the role of the Office of Naval Research in the development of the scheduling literature during the first decade (1954–1963). We also provide a critical analysis of the papers by Johnson and Smith. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 335–344, 2015

It is known that the proportionate flow shop minimum makespan F m / p r p t / C max problem is solved optimally by any permutation job sequence. We show that the F m / p r p t / C max problem is at least ordinary NP-hard when missing operations are allowed and present some solvable cases. We then consider the standard proportionate flow shop problem (with no missing operations) and show that the solution algorithms for a class of single-machine due date assignment problems can be extended/generalized to the corresponding proportionate flow shop problems. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 98–106, 2015

We consider the two-machine no-wait open shop minimum makespan problem in which the determination of an optimal solution requires an optimal pairing of the jobs followed by the optimal sequencing of the job pairs. We show that the required enumeration can be curtailed by reducing the pair sequencing problem for a given pair set to a traveling salesman problem which is equivalent to a two-machine no-wait flow shop problem solvable in O ( n log n ) time. We then propose an optimal O ( n log n ) algorithm for the proportionate problem with equal machine speeds in which each job has the same processing time on both machines. We show that our O ( n log n ) algorithm also applies to the more general proportionate problem with equal machine speeds and machine-specific setup times. We also analyze the proportionate problem with unequal machine speeds and conclude that the required enumeration can be further curtailed (compared to the problem with arbitrary job processing times) by eliminating certain job pairs from consideration.

We consider the single-machine maximum earliness problem with rejection.We present an O(nlogn) algorithm for the problem.We consider the single-machine total earliness problem with rejection.We present a pseudo-polynomial time algorithm for the problem. We present optimal algorithms for single-machine scheduling problems with earliness criteria and job rejection and compare them with the algorithms for the corresponding problems with tardiness objectives. We present an optimal O(nlogn) algorithm for minimizing the maximum earliness on a single machine with job rejection. Our algorithm also solves the bi-criteria scheduling problem is which the objective is to simultaneously minimize the maximum earliness of the scheduled jobs and the total rejection cost of the rejected jobs. We also show that the optimal pseudo-polynomial time algorithm for the total tardiness problem with job rejection can be used to solve the corresponding total earliness problem with job rejection.

We investigate the solvability of two single-machine scheduling problems when the objective is to identify among all job subsets with cardinality k,1≤k≤n, the one that has the minimum objective function value. For the single-machine minimum maximum lateness problem, we conclude that the problem is solvable in O(n2) time using the proposed REMOVE algorithm. This algorithm can also be used as an alternative to Moore's algorithm to solve the minimum number of tardy jobs problem by actually solving the hierarchical problem in which the objective is to minimize the maximum lateness subject to the minimum number of tardy jobs. We then show that the REMOVE algorithm cannot be used to solve the general case of the single-machine total-weighted completion time problem; we derive sufficient conditions among the job parameters so that the total weighted completion time problem becomes solvable in O(n2) time. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 449–453, 2013

Ordered flow shop models have appeared in the literature since the mid-1970s and proportionate flow shop models have appeared since the early 1980s. We provide a detailed review of these models along with some analysis and potential topics for future research. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013

We consider a static, single operation, non-pre-emptive, deterministic scheduling problem in which a set of n jobs is to be processed on k identical machines. Jobs assigned to each machine have a common due date. The number of machines (k) is unknown. Activating a machine will require additional costs to be incurred. The objective is to find an optimal sequence, the optimal number of machines (k), and the respective due dates to minimize the weighted sum of earliness, tardiness, and machine activation costs. We propose a polynomial time algorithm to solve the problem.

We consider a single machine static and deterministic scheduling problem in which jobs have a common due window. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The objective is to find the optimal size and location of the window as well as an optimal sequence to minimise a cost function based on earliness, tardiness, window size, and window location. We propose an O(n log n) algorithm to solve the problem.

A static deterministic single machine scheduling problem with a common due window is considered. Job processing times are controllable to the extent that they can be reduced, up to a certain limit, at a cost proportional to the reduction. The window location and size, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the window location, its size, processing time reduction as well as job earliness and tardiness. We show that the problem can be formulated as an assignment problem and thus can be solved with well-known algorithms.

We consider the static deterministic single machine scheduling problem in which all jobs have a common due window. Jobs that are completed within the window incur no penalty. The objective is to find the optimal sequence and the optimal common due window location given that the due window size is a problem parameter such that the weighted sum of earliness, tardiness, and due window location penalties is minimized. We propose an O( n log n ) algorithm to solve the problem. We also consider two special cases for which simple solutions can be obtained.

A heuristic (P-S-K) is presented in this paper for minimizing the mean tardiness for the single machine sequencing problem. This heuristic is compared with other available construction heuristics from the literature like the Wilkerson-Irwin (W-I), Holsenback-Russel (H-R), and API heuristics. It is shown that P-S-K yields better results than the other methods on a wide range of problems. Furthermore, as due dates become tight, P-S-K is substantially better than the other methods with respect to computational time.

Jafari and Moslehi (J Glob Optim 54:389---404, 2012) state that certain single-machine scheduling problems with linear job deterioration are NP-hard. We show that this is not the case for the maximum lateness minimization problem and point out the issues in the analysis of Jafari and Moslehi (J Glob Optim 54:389---404, 2012).

In this paper we consider scheduling n single operation jobs with a common due date on m non-identical machines (in parallel) so as to minimize the sum of the absolute lateness. We reduce the problem to a transportation problem that can be solved by a polynomial time algorithm. Furthermore, we consider the problem in the case of identical machines and we give a heuristic algorithm to minimize makespan among all schedules that minimize the absolute lateness problem.

We consider a static single-machine sequencing problem which job processing times are controllable variables with linear costs. All jobs have a common due data. The objective is to find optimal processing times, an optimal due date and an optimal sequence which will minimize a cost function containing earliness cost, tardiness cost, and total processing cost.

We consider the classical two-machine flowshop sequencing problem with the following additional constraint. When a job is completed on the first machine it must be transported to the second machine; a single transporter is available. A completed job on the first machine will block the machine if the transporter is in transit. A constructive algorithm to minimize makespan is presented in the paper.

This paper considers the classical nXm flow shop sequencing problem. An improved branch and bound procedure is proposed. Computational experience shows that the proposed procedure is more efficient compared to the existing optimizing procedures.

The objective is to minimize makespan for a special case of flow shop problems subject to the constraint that no in-process waiting is allowed. Several new results are proposed.

A flowshop sequencing problem having an ordered processing time matrix is defined. Job and machine characteristics resulting in processing time relationships that have logical and practical bases are discussed. An optimizing solution procedure for a special class of ordered matrix problem is presented along with proof of optimality.

An expression describing average output of a series of K servers with interstage queues of capacity n is presented. This expression gives output rates that are highly correlated with empirical results obtained in other investigations.

This paper describes a study of an industrial sequencing/scheduling problem. The study contains the definition of the problem, data requirements and examination of solution technique. Definition of the problem is discussed from the aspect of uniqueness of the specific system. Discussion of data requirements includes availability and accuracy, while examination of solution technique considers limitation of time, computer capacity, etc., as well as the possibility of imbedding available algorithms into the solution procedure. Conclusions are presented relative to the use of the case study approach in sequencing/scheduling research.

Given processing times of n jobs on a single machine with penalties for earliness and tardiness and penalties associated with assignment of due-dates, the objective is to select optimal due-dates and optimal sequence. Scheduling procedure for the solution of this problem is presented along with proof of optimality and illustrative numerical examples.

We consider an n job, one machine scheduling problem in which all jobs have a common due date. The objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. This penalty function is based on the due date value and on the earliness or the lateness of each job in the selected sequence. We present a polynomial bound scheduling algorithm for the solution of this problem along with the proof of optimality, a numerical example and discuss some extensions.

A flow shop sequencing problem with ordered processing time matrices is considered. A convex property for the makespan sequences of such problems is discussed. On the basis of this property an efficient optimizing algorithm is presented. Although the proof of optimality has not been developed, several hundred problems were solved optimally with this procedure.

The ordered matrix flow shop problem with no passing of jobs is considered. In an earlier paper, the authors have considered a special case of the problem and have proposed a simple and efficient algorithm that finds a sequence with minimum makespan for a special problem. This paper considers a more general case. This technique is shown to be considerably more efficient than are existing methods for the conventional flow shop problems.

The problem studied is that of two-machine job shop sequencing where some jobs are processed first on machine 1 and then on machine 2, while the remaining jobs are processed in the reverse order. The objective is to determine an ordered sequence which minimizes the total processing time, subject to some specified lag time constraints. A rule is given for determining two different sequences for the two machines which represent an optimal solution.

Linear programming problems with upper bounded variables can be solved by regular simplex method by considering upper bounding constraints as explicit constraints of the problem. However, more efficient methods exist which consider these upper bound constraints implicitly. When parametric analysis for problems with upper bounds is to be carried out, one can use the regular parameter analysis by considering the upper bound constraints explicitly. This paper develops formulas for parametric analysis where upper bound constraints are used implicitly, thus reducing the size of the basic matrix.