Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2007.11.035 Byline: T.C.E. Cheng (a), B.M.T. Lin (b) Keywords: Flowshop; Makespan; Johnson's rule; Composite job; Relocation problem Abstract: Two-machine flowshop scheduling to minimize makespan is one of the most well-known classical scheduling problems. Johnson's rule for solving this problem has been widely cited in the literature. We introduce in this paper the concept of composite job, which is an artificially constructed job with processing times such that it will incur the same amount of idle time on the second machine as that incurred by a chain of jobs in a given processing sequence. This concept due to Kurisu first appeared in 1976 to deal with the two-machine flowshop scheduling problem involving precedence constraints among the jobs. We show that this concept can be applied to reduce the computational time to solve some related scheduling problems. We also establish a link between solving the two-machine flowshop makespan minimization problem using Johnson's rule and the relocation problem introduced by Kaplan. We present an intuitive interpretation of Johnson's rule in the context of the relocation problem. Author Affiliation: (a) Department of Logistics, The Hong Kong Polytechnic University, Kowloon, Hong Kong (b) Department of Information and Finance Management, Institute of Information Management, National Chiao Tung University, Hsinchu 300, Taiwan Article History: Received 26 April 2007; Accepted 5 November 2007

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.10.021 Byline: B.M.T. Lin (a), A.V. Kononov (b) Keywords: Order scheduling; Number of late jobs; Approximability; Approximation algorithm; Multicover problem Abstract: In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for the two-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date. Author Affiliation: (a) Department of Finance and Information Management, Institute of Information Management, National Chiao Tung University, Taiwan (b) Sobolev Institute of Mathematics, Novosibirsk, Russia Article History: Received 12 January 2006; Accepted 13 October 2006 Article Note: (footnote) [star] This research is supported by Taiwan-Russia joint grant under contract numbers NSC94-2416-H-009-013 and RP05H01(05-06-90606-HHCa).

This note presents complexity results for a single-machine scheduling problem of minimizing the number of late jobs. In the studied problem, the processing times of the jobs are defined by positional learning effects. A recent paper proposed a polynomial time algorithm for the case with a common due date and conjectured the general problem to be NP-hard. We confirm that the general problem is strongly NP-hard and show that the studied problem remains NP-hard even if there are only two different due-date values. Keywords: single-machine scheduling; learning effect; late job; NP-hardness

This paper addresses a three-machine assembly-type flowshop scheduling problem, which frequently arises from manufacturing process management as well as from supply chain management. Machines one and two are arranged in parallel for producing component parts individually, and machine three is an assembly line arranged as the second stage of a flowshop for processing the component parts in batches. Whenever a batch is formed on the second-stage machine, a constant setup time is required. The objective is to minimize the makespan. In this study we establish the strong NP-hardness of the problem for the case where all the jobs have the same processing time on the second-stage machine. We then explore a useful property, based upon which a special case can be optimally solved in polynomial time. We also study several heuristic algorithms to generate quality approximate solutions for the general problem. Computational experiments are conducted to evaluate the effectiveness of the algorithms. Keywords: Two-stage flowshop; Batch scheduling; Makespan; NP-hardness; Heuristics, 1. Introduction In this paper we study an assembly-type production scheduling problem, which can be used to model the coordination of production scheduling between cooperative parties in a supply chain. [...]

The celebrated Johnson’s algorithm to solve the two-machine flowshop scheduling problem to minimise the makespan plays a prominent role in scheduling research. In using resource-constrained scheduling to interpret Johnson’s algorithm in teaching scheduling theory and operations management, we have received positive student feedback on the perceived intuition. We demonstrate this idea and show that the resource-constrained scheduling concept also helps simplify the proofs of some classical scheduling results. [ABSTRACT FROM PUBLISHER]

This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be N P-hard in the literature. In this paper, we design branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding proeess such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases. Keywords: Operations scheduling; Linear deterioration; Maximum lateness; Branch-and-bound algorithm; Heuristic algorithm, 1. Introduction In the deterministic production and operations scheduling literature, most of the research works assume that the operation or processing times are fixed once they are given. In the [...]

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on m identical parallel machines. The jobs have to be batched as well as scheduled. The completion time of a job is defined as the completion time of the batch containing it. A constant set-up time is incurred whenever a batch is formed. The problem is to batch and schedule jobs so that the total completion time of the jobs is minimized. We first present some properties and then develop a dynamic programming algorithm to solve this problem. The running time of our algorithm is O([mn.sup.m + 1]). When job processing times are identical, we show that the problem reduces to the corresponding single-machine problem, which has been well solved in the literature., 1. Introduction There are n independent non-preemptive jobs j [element of] N = {1, ..., n} to be processed on m identical parallel machines. Each job j has a processing [...]

The minimization of the makespan in the 3-machine assembly-type flowshop scheduling problem is examined. An assembly-type flowshop is a production system in which component parts are fabricated in job shops, from which the components are fed into an assembly line for final assembly operations. Minimizing the makespan or the time used to complete all orders is a strongly NP-complete problem. Special cases solvable in polynomial time are analyzed and their solution algorithms presented. The problem's NP-completeness suggests a branch and bound solution scheme, for which three heuristics are proposed. The error bounds of these heuristics are analyzed. This scheduling problem is strongly NP-complete even in the more realistic multistage systems.

We consider a parallel-machine scheduling problem of minimizing the total completion time. The processing time of a job is a linear function of its starting time and deterioration rate. This problem is known to be NP-hard, even for the case with two machines. In this note, we generalize an existing lower bound for the two-machine case to the general case with an arbitrary number of machines. Despite the generalization concerning machine number, our bound has one extra term that makes our bound tighter than the existing one. doi: 10.1057/palgrave.jors.2602208 Published online 26 April 2006 Keywords: parallel-machine scheduling; time-dependent processing time; lower bound

We propose from the perspective of operations scheduling a novel model of the refurbishing process in recycling management. We model the refurbishing process as a two-stage flowshop that dismantles products into parts in stage one and refurbishes the parts on dedicated machines in stage two. The model also features that the performance measure of a schedule is defined by operation-based completion times, which is different from the job-based performance measures traditionally adopted in the scheduling literature. We analyse the optimality properties and computational complexity of some special cases of the problem. We derive lower bounds on the optimal solution based on a disaggregation technique and the assignment problem, and develop dominance rules incorporating estimates of the effects of partial schedules on unscheduled jobs. We present a heuristic approach, based on LP relaxation, and analyse its performance ratio. We also develop two metaheuristic algorithms, based on iterated local search and ant colony optimisation, to produce approximate solutions. The results of computational experiments show that the metaheuristics generate better solutions than the simple weighted shortest processing time dispatching rule, and the NEH-based and CDS-based algorithms, which are commonly deployed to treat the classical two-machine flowshop scheduling problem. [ABSTRACT FROM AUTHOR]

We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution. [ABSTRACT FROM AUTHOR]

The ant colony optimization is a meta-heuristic inspired by knowledge sharing amongst ants using pheromone, which serves as a kind of collective memory. Since the past few years, there have been several successful applications of this new approach for finding approximate solutions for computationally difficult problems in reasonable times. In this paper, we study the generalized minimum spanning tree problem that involves the design of a minimum weight connected network spanning at least one node out of every disjoint subset of the nodes in a graph. This problem has a wealth of pertinence to a wide range of applications in different areas. As the problem is known as computationally challenging, we adopt the ant colony optimization strategy and present a new solution method, called Ant-Tree, to develop approximate solutions. As an initial attempt, our study aims to provide an investigation of the ant colony optimization approach for coping with tree optimization problems. Through computational experiments, we compare the performances of our approach and the method available in the literature. Numerical results indicate that the proposed method is effective in producing quality approximate solutions. [ABSTRACT FROM AUTHOR]