Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.12.013 Byline: Christos Koulamas, Sushil Gupta, George J. Kyparisis Keywords: Scheduling; Single-machine; Variable processing times Abstract: We present a unified analysis for single-machine scheduling problems in which the actual job processing times are controlled by either a linear or a convex resource allocation function and also vary concurrently depending on either the job's position in the sequence and/or on the total processing time of the already processed jobs. We show that the problem is solvable in O(nlogn) time by using a weight-matching approach when a convex resource allocation function is in effect. In the case of a linear resource allocation function, we show that the problem can be solved in O(n.sup.3) time by using an assignment formulation. Our approach generalizes the solution approach for the corresponding problems with controllable job processing times to incorporate the variability of the job processing times stemming from either the job's position in the sequence and/or the total processing time of the already processed jobs. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, United States Article History: Received 5 June 2009; Accepted 8 December 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.02.008 Byline: Christos Koulamas, George J. Kyparisis Keywords: Scheduling; Uniform parallel machines; LPT; Approximation algorithms Abstract: We propose a modified longest processing time (MLPT) heuristic algorithm for the two uniform machine makespan minimization problem. The MLPT algorithm schedules the three longest jobs optimally first, followed by the remaining jobs sequenced according to the LPT rule. We prove the tight worst-case ratio bound of 1.5=1.2247 for the MLPT algorithm which is an improvement over the tight worst-case ratio bound of 1.28 for the LPT algorithm. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, USA Article History: Received 13 June 2007; Accepted 11 February 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2007.08.015 Byline: Christos Koulamas, George J. Kyparisis Keywords: Scheduling; Single machine; Lateness; Due date assignment Abstract: We consider a single-machine scheduling problem in which due dates are linear functions of the job waiting-times and the objective is to minimize the maximum lateness. An optimal sequence is constructed by implementing an index-based priority rule for a fixed value of the due date normalizing constant k. We determine in polynomial time all the k value ranges so that the optimal sequence remains the same within each range. The optimal due dates are computed as linear functions of the global optimal value of k. The overall procedure is illustrated in a numerical example. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, United States Article History: Received 14 September 2006; Accepted 14 August 2007

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.03.066 Byline: Christos Koulamas, George J. Kyparisis Keywords: Scheduling; Single-machine; Setup times Abstract: 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. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, University Park, Miami, FL 33199, United States Article History: Received 22 October 2005; Accepted 18 March 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2007.04.013 Byline: Christos Koulamas, George J. Kyparisis Keywords: Scheduling; Parallel machines; LPT; Approximation algorithms Abstract: We propose an off-line delayed-start LPT algorithm that sequences the first (longest) 5 jobs optimally and the remaining jobs according to the LPT principle on two identical parallel machines. We show that this algorithm has a sharper tight worst-case ratio bound than the traditional LPT algorithm for the sum of squares of machine completion times minimization problem. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, USA Article History: Received 5 October 2006; Accepted 10 April 2007

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.07.027 Byline: Christos Koulamas, George J. Kyparisis Keywords: Scheduling; Flow shop; Uniform machines; Absolute performance bound; Approximation algorithms Abstract: We study the problem of minimizing the makespan in a two-stage assembly flow shop scheduling problem with uniform parallel machines. This problem is a generalization of the assembly flow shop problem with concurrent operations in the first stage and a single assembly operation in the second stage. We propose a heuristic with an absolute performance bound which becomes asymptotically optimal as the number of jobs becomes very large. We show that our results slightly improve earlier results for the simpler assembly flow shop problem (without uniform machines) and for the two-stage hybrid flow shop problem with uniform machines. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, USA Article History: Received 10 March 2006; Accepted 20 July 2006

In this note a tight worst-case ratio bound is derived for a heuristic for the three-stage flexible flowshop makespan minimization problem. It is shown that the derived bound is the best available for the three-stage problem. Furthermore, the derived bound can be used to improve the best available worst-case ratio bound for the flexible flowshop makespan minimization problem with an arbitrary odd number of stages. Keywords: Scheduling, flexible flowshop, parallel machines, approximation algorithms, 1. Introduction In this note, we consider three-stage flexible flowshop problems with identical parallel machines per stage and with the objective of minimizing the maximum job completion time (makespan). The [...]

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.01.030 Byline: Christos Koulamas, George J. Kyparisis Keywords: Scheduling; Single machine; Flowshop; Shortest processing time; Learning; Optimal algorithms Abstract: We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment. Author Affiliation: Department of Decision Sciences and Information Systems, College of Business Administration, Florida International University, University Park Campus, Miami, FL 33199, USA Article History: Received 26 October 2004; Accepted 9 January 2006

A study on makespan problems of single and double machine flowshops with relation to reduction of processing time is presented.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.06.017 Byline: George J. Kyparisis, Christos Koulamas Keywords: Flow shop scheduling; Flexible flow shop; Approximation/heuristic; Worst-case analysis Abstract: We consider the two-stage flexible flow shop makespan minimization problem with uniform parallel machines. Soewandi and Elmaghraby [Soewandi, H., Elmaghraby, S., 2003. Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan. IIE Transaction 35, 467-477] developed a heuristic (S-E) and derived a machine speed-dependent worst-case ratio bound for it. We point out that this bound works well when the uniform machines have approximately equal speeds but is not indicative of the performance of the S-E heuristic when the machine speeds are in a wide range. Motivated by this observation, we propose an alternative tight machine-speed dependent worst-case bound for the S-E heuristic that works well when the machine speeds vary significantly. We then combine the two speed-dependent ratio bounds into a speed-independent bound. Our findings facilitate the narrowing of the gap between experimental performance and worst-case bound for the S-E heuristic. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, Miami FL 33199, USA Article History: Received 27 July 2004; Accepted 8 June 2005

The makespan minimization concept for managing flow-shop scheduling in uniform production systems is presented.

A heuristic is developed to explain a two-stage flexible flow shop makespan minimization problem with uniform parallel machines.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2004.05.034 Byline: Jatinder N.D. Gupta (a), Christos Koulamas (b), George J. Kyparisis (b) Keywords: Production scheduling; Multiple machines; Flowshop heuristics; Analysis of algorithms Abstract: This paper reviews the known worst-case ratios and absolute performance guarantees of various flowshop heuristics to minimize makespan. The absolute and worst-case performance ratio bounds are compared using probabilistic analysis. The best absolute performance bound is shown to outperform the tightest worst-case ratio bound with 99% probability when a certain minimum number of jobs is present. Thus, probabilistic analysis may provide a bridge between the absolute and worst-case performance guarantees of heuristic algorithms. Author Affiliation: (a) Department of Accounting and Information Systems, University of Alabama in Huntsville, College of Administrative Science, Huntsville, AL 35899, USA (b) Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, USA Article History: Received 24 July 2003; Accepted 17 May 2004

A study is conducted by comparing performance ratios of flowshop heuristic algorithms to analyze the performance guarantee of these algorithms to minimize makespan.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2004.05.017 Byline: George J. Kyparisis, Christos Koulamas Keywords: Scheduling; Makespan; Flexible flow shop; Uniform machines; Absolute performance guarantee; Approximation algorithms Abstract: We consider the multistage flexible flow shop scheduling problem with uniform parallel machines in each stage and the objective of minimizing makespan. We develop a general class of heuristics for this strongly NP-hard problem that extend several well-known heuristics for the corresponding embedded serial flow shop problem, and obtain absolute performance guarantees for heuristics in this class by building on similar absolute performance guarantees for the corresponding serial flow shop heuristics. Our approach is quite robust, since it can extend any heuristic for the serial flow shop problem (with an absolute performance guarantee) to a similar one for the flexible flow shop problem with uniform parallel machines. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, USA Article History: Received 23 June 2003; Accepted 13 May 2004

The multistage flexible flow shop scheduling problem with uniform parallel machines in each stage and the objective of minimizing makespan is examined. A heuristic approach to solve this problem is presented.

We consider flow-shop scheduling problems with regular (nondecreasing) objective functions such as the minimization of makespan in the presence of arbitrary precedence constraints, the weighted sum of job completion times in the presence of series-parallel precedence constraints, the discounted total weighted completion time, and the sum of the quadratic job completion times. We present algorithms with tight worst-case performance bounds for all of these problems by utilizing the optimal permutations for the corresponding single-machine problems. We also investigate the asymptotic optimality of our algorithms., 1. Introduction One of the earliest ideas in flow shop scheduling was the development of heuristics with tight worst-case bounds for NP-hard problems by utilizing the optimal permutation (when available) [...]

The makespan minimization problem is considered on uniform parallel machines in the presence of release times. A heuristic is developed for this NP-hard problem and derived a tight worst-case ratio bound for the heuristic independence of the machine speeds.

The concurrent flowshop-scheduling problem with the makespan objective function is discussed. In the problem each job consists of several components each of which is processed on a dedicated flowshop.

This paper addresses the assembly-line scheduling problem with concurrent operations per stage and parallel machines. This problem can be briefly described as the problem of sequencing a predetermined set of […]

Research describing the minimization of tardiness for a single machine is presented. In particular a polynomial time algorithm is developed to investigate the constraints of deadlines and release times.

An optimal heuristic for the m-stage flowshop problem is considered, with flexible stage ordering.

Research is presented concerning the development of polynomial time algorithms suitable for use in machine open shop and flow shop makespan problems. Both problems involve the use presence of a critical machine.

The problem of choosing a subset of N projects under multiple sequence-dependent resource constraints is considered. Known as the project selection problem, it is a nonlinear (0-1) integer problem that seeks to maximize the net present value of total returns. To solve it, two heuristics that converge to near solutions within O(N3K) and O(N4K) time are described. The first refines a feasible solution derived by a greedy procedure while the second combines it with steps zero and one of the M heuristic.

An project selection model has been developed for identifying benefit, resource and technical interdependencies among various information system (IS) projects. The model takes into account the resource and logical constraints to determine the different parameters that affect the cost of IS projects. It has been used in the analysis of an IS project by a large service organization with favorable results.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.02.020 Byline: Christos Koulamas, George J Kyparisis Keywords: Supply chains; Competition; Pricing; Equilibrium Abstract: The study of the effects of downstream entry on upstream pricing has revealed the counter-intuitive result of the supplier's pricing policy being invariant to a new downstream entry under an isoelastic inverse demand function. We show that this counter-intuitive result is reversed when a new downstream entry affects downstream efficiency. We show that in the presence of increased post-entry downstream efficiency the supplier increases the wholesale price by taking advantage of the increased retail efficiency and competition. We also investigate the applicability of our results under other types of inverse demand functions. Author Affiliation: College of Business Administration, Florida International University, Department of Decision Science and Information Systems, Miami, FL 33199, United States Article History: Received 27 May 2008; Accepted 16 February 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.01.031 Byline: Christos Koulamas, George J. Kyparisis Keywords: Flow shop sequencing; Proportionate flow shop; Makespan; Approximation algorithms Abstract: Choi, B.-C., Yoon, S.-H., Chung, S.-J., 2007. Minimizing maximum completion time in a proportionate flow shop with one machine of different speed. European Journal of Operational Research 176, 964-974 consider the proportionate flow shop with a slow bottleneck machine and propose the SLDR heuristic for it. derive a data-dependent worst-case ratio bound for the SLDR heuristic which is then bounded by two. In this note, we show that the tight worst-case ratio bound of the SLDR heuristic is 3/2. Author Affiliation: Department of Decision Sciences and Information Systems, Florida International University, College of Business Administration, Miami, FL 33199, United States Article History: Received 28 December 2006; Accepted 23 January 2008