Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2010.05.017 Byline: Yingxue Zhao (a)(b), Shouyang Wang (a), T.C.E. Cheng (c), Xiaoqi Yang (d), Zhimin Huang (e)(f) Keywords: Supply chain management; Cooperative game; Option contract; Negotiating power; Channel coordination Abstract: Manufacturer-retailer supply chains commonly adopt a wholesale price mechanism. This mechanism, however, has often led manufacturers and retailers to situations of conflicts of interest. For example, due to uncertain market demand, retailers prefer to order flexibly from manufacturers so as to avoid incurring inventory costs and to be able to respond flexibly to market changes. Manufacturers, on the other hand, prefer retailers to place full orders as early as possible so that they can hedge against the risks of over- and under-production. Such conflicts between retailers and manufacturers can result in an inefficient supply chain. Motivated by this problem, we take a cooperative game approach in this paper to consider the coordination issue in a manufacturer-retailer supply chain using option contracts. Using the wholesale price mechanism as a benchmark, we develop an option contract model. Our study demonstrates that, compared with the benchmark based on the wholesale price mechanism, option contracts can coordinate the supply chain and achieve Pareto-improvement. We also discuss scenarios in which option contracts are selected according to individual supply chain members' risk preferences and negotiating powers. Author Affiliation: (a) Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, PR China (b) School of International Trade and Economics, University of International Business and Economics, Beijing 100029, PR China (c) Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, PR China (d) Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, PR China (e) School of Business, Adelphi University, Garden City, NY 11530, USA (f) School of Business, Renmin University of China, Beijing 100872, PR China Article History: Received 27 May 2009; Accepted 13 May 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2010.05.034 Byline: C.T. Ng (a), M.S. Barketau (b), T.C.E. Cheng (a), Mikhail Y. Kovalyov (b) Keywords: Complexity theory; Scheduling; Subset Product; FPTAS; Systems reliability Abstract: Problem Product Partition differs from the NP-complete problem Partition in that the addition operation is replaced by the multiplication operation. Furthermore it differs from the NP-complete problem Subset Product in that it does not contain the product value B in its input. We prove that problem Product Partition and several of its modifications are NP-complete in the strong sense. Our results imply the strong NP-hardness of a number of scheduling problems with start-time-dependent job processing times and a problem of designing a reliable system with a series-parallel structure. It should be noticed that the strong NP-hardness of the considered optimization problems does not preclude the existence of a fully polynomial time approximation scheme (FPTAS) for them. We present a simple FPTAS for one of these problems. Author Affiliation: (a) Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong (b) United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus Article History: Received 23 September 2009; Accepted 19 May 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.12.012 Byline: Guowei Hua (a)(c), Shouyang Wang (b), T.C.E. Cheng (c) Keywords: Supply chain management; Dual channel; Internet/direct marketing; E-commerce; Game theory Abstract: Manufacturers today are increasingly adopting a dual channel to sell their products, i.e., the traditional retail channel and an online direct channel. Empirical studies have shown that service quality (we focus on the delivery lead time of the direct channel) even goes beyond product price as one of the major factors influencing consumer acceptance of the direct channel. Delivery lead time has significant effects on demand, profit, and pricing strategy. However, there is scant literature addressing the decision on the promised delivery lead time of a direct channel and its impact on the manufacturer's and retailer's pricing decisions. To fill this gap, we examine the optimal decisions of delivery lead time and prices in a centralized and a decentralized dual-channel supply chain using the two-stage optimization technique and Stackelberg game, and analyze the impacts of delivery lead time and customer acceptance of a direct channel on the manufacturer's and retailer's pricing behaviours. We analytically show that delivery lead time strongly influences the manufacturer's and the retailer's pricing strategies and profits. Our numerical studies reveal that the difference between the demand transfer ratios in the two channels with respect to delivery lead time and direct sale price, customer acceptance of the direct channel, and product type have great effects on the lead time and pricing decisions. Author Affiliation: (a) School of Economics and Management, Beijing Jiaotong University, Beijing 100044, China (b) Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China (c) Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China Article History: Received 17 September 2008; Accepted 9 December 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.05.021 Byline: Min Ji (a)(b), T.C.E. Cheng (b) Keywords: Batch scheduling; Makespan; Computational complexity; FPTAS Abstract: We consider a scheduling problem in which n jobs are to be processed on a single machine. The jobs are processed in batches and the processing time of each job is a simple linear function of its waiting time, i.e., the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. The objective is to minimize the makespan, i.e., the completion time of the last job. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when Ba[c]1/2U for a variable U[greater than or equal to]2 or B[greater than or equal to]U for any constant U[greater than or equal to]2. For the case of Ba[c]1/2U, we present a dynamic programming algorithm that runs in pseudo-polynomial time and a fully polynomial time approximation scheme (FPTAS) for any constant U[greater than or equal to]2. Furthermore, we provide an optimal linear time algorithm for the special case where the jobs are subject to a linear precedence constraint, which subsumes the case where all the job growth rates are equal. Author Affiliation: (a) College of Computer Science and Information Engineering, Zhejiang Gongshang University, Hangzhou 310018, PR China (b) Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Kowloon, Hong Kong Article History: Received 16 October 2008; Accepted 14 May 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.02.006 Byline: L. Yang, C.T. Ng, T.C.E. Cheng Keywords: Distribution centre; Vendor-managed inventory system; Order-up-to-level policy; Location problem Abstract: This paper evaluates the effects of the distribution centre (DC) in a vendor-managed inventory (VMI) system comprising one manufacturer, one DC and n retailers. Adopting the order-up-to-level (OUL) replenishment policy, the system aims to maximize the overall system profit. We propose a model to evaluate the system performance by considering the scale of the distribution network, influential cost factors, demand distribution, planning horizon, and facility locations. From the viewpoint of a supply chain, we examine the DC's effects on the system in terms of net profit. Our findings reveal that the DC has effects on demand variance and system profit, and there are some dominant factors that affect the overall system performance. The DC may lead to different system performance under a variety of cost factors, and in some situations, the DC may negatively affect system performance. We also suggest some innovative uses of the DC's location to help enhance system performance. Author Affiliation: Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong Article History: Received 26 March 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.01.040 Byline: C.T. Ng (a), Mikhail Y. Kovalyov (b), T.C.E. Cheng (a) Keywords: Capacitated economic lot-sizing problem; Fully polynomial time approximation scheme Abstract: The single-item capacitated economic lot-sizing (CELS) problem is a fundamental problem of production and inventory management. The first fully polynomial approximation scheme (FPTAS) for this problem with concave cost functions was developed by Van Hoesel and Wagelmans [C.P.M. Van Hoesel, A.P.M. Wagelmans, Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems, Mathematics of Operations Research 26 (2001) 339-357]. Chubanov et al. [S. Chubanov, M.Y. Kovalyov, E. Pesch, An FPTAS for a single-item capacitated economic lot-sizing problem, Mathematical Programming Series A 106 (2006) 453-466] later presented a sophisticated FPTAS for the general case of the CELS problem with a monotone cost structure. In this paper, we present a better FPTAS for this case. The ideas and presentation of our FPTAS are simple and straightforward. Its running time is about n.sup.4/I[micro].sup.2 times faster than that of Chubanov et al. [5], where n is the number of production periods and I[micro] is the anticipated relative error of the approximate solution. Author Affiliation: (a) Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong (b) Belarusian State University, and United Institute of Informatics Problems, National Academy of Sciences of Belarus, Nezavisimosti 4, 220030 Minsk, Belarus Article History: Received 10 January 2008; Accepted 22 January 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.01.008 Byline: Qiu-Hong Zhao (a), T.C.E. Cheng (b) Keywords: Vendor managed inventory system; Distribution center; Modification ability; Order-up-to-level policy; Location Abstract: This paper considers a two-level vendor managed inventory (VMI) system comprising a distribution center (DC) and a retailer. Both the DC's and the retailer's replenishment decisions follow the order-up-to-level policy and aim at maximizing the profit of the overall system. We critically examine the potential of the DC's ability to modify delivery decisions, identify and quantify the cost factors that influence the DC's modification ability, establish a relationship between the DC's location and its modification ability, and show the trade-off between the DC's modification ability and related costs. Our analysis provides a new insight into the role of the DC and reveals the full potential of the VMI system. Our findings and their practical implications, demonstrated with the aid of computational examples, are helpful for enhancing the practice of VMI at both strategic and operational levels. Author Affiliation: (a) School of Economics and Management, Beihang University, Beijing 100083, China (b) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong Article History: Received 31 January 2007; Accepted 7 January 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2007.12.033 Byline: Xiuli Wang (a)(b), T.C.E. Cheng (b) Keywords: Scheduling; Supply and delivery; Heuristics; Performance bounds Abstract: In this paper we study a scheduling model that simultaneously considers production scheduling, material supply, and product delivery. One vehicle with limited loading capacity transports unprocessed jobs from the supplier's warehouse to the factory in a fixed travelling time. Another capacitated vehicle travels between the factory and the customer to deliver finished jobs to the customer. The objective is to minimize the arrival time of the last delivered job to the customer. We show that the problem is NP-hard in the strong sense, and propose an O(n) time heuristic with a tight performance bound of 2. We identify some polynomially solvable cases of the problem, and develop heuristics with better performance bounds for some special cases of the problem. Computational results show that all the heuristics are effective in producing optimal or near-optimal solutions quickly. Author Affiliation: (a) School of Economics and Management, Nanjing University of Science and Technology, Nanjing, China (b) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong Article History: Received 2 March 2007; Accepted 27 December 2007

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.2007.08.019 Byline: T.C.E. Cheng (a), C.T. Ng (a), J.J. Yuan (a)(b) Keywords: Scheduling; Single machine; Multi-operation jobs; Job-batch restriction; SPT-agreeability Abstract: We consider the problem of scheduling multi-operation jobs on a singe machine to minimize the total completion time. Each job consists of several operations that belong to different families. In a schedule each family of job operations may be processed as batches with each batch incurring a set-up time. A job is completed when all of its operations have been processed. We first show that the problem is strongly NP-hard even when the set-up times are common and each operation is not missing. When the operations have identical processing times and either the maximum set-up time is sufficiently small or the minimum set-up time is sufficiently large, the problem can be solved in polynomial time. We then consider the problem under the job-batch restriction in which the operations of each batch is partitioned into operation batches according to a partition of the jobs. We show that this case of the problem can be solved in polynomial time under a certain condition. Author Affiliation: (a) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China (b) Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China Article History: Received 6 April 2006; Accepted 20 August 2007

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.06.060 Byline: Ali Allahverdi (a), C.T. Ng (b), T.C.E. Cheng (b), Mikhail Y. Kovalyov (c) Keywords: Scheduling; Setup time; Setup cost; Survey (review); Single machine; Parallel machines; Flow shop; Job shop; Open shop Abstract: The first comprehensive survey paper on scheduling problems with separate setup times or costs was conducted by [Allahverdi, A., Gupta, J.N.D., Aldowaisan, T., 1999. A review of scheduling research involving setup considerations. OMEGA The International Journal of Management Sciences 27, 219-239], who reviewed the literature since the mid-1960s. Since the appearance of that survey paper, there has been an increasing interest in scheduling problems with setup times (costs) with an average of more than 40 papers per year being added to the literature. The objective of this paper is to provide an extensive review of the scheduling literature on models with setup times (costs) from then to date covering more than 300 papers. Given that so many papers have appeared in a short time, there are cases where different researchers addressed the same problem independently, and sometimes by using even the same technique, e.g., genetic algorithm. Throughout the paper we identify such areas where independently developed techniques need to be compared. The paper classifies scheduling problems into those with batching and non-batching considerations, and with sequence-independent and sequence-dependent setup times. It further categorizes the literature according to shop environments, including single-machine, parallel machines, flow shop, no-wait flow shop, flexible flow shop, job shop, open shop, and others. Author Affiliation: (a) Department of Industrial and Management Systems Engineering, Kuwait University, P.O. Box 5969, Safat, Kuwait (b) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong (c) Faculty of Economics, Belarusian State University, and United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus Article History: Received 16 October 2005; Accepted 12 June 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.05.001 Byline: Chin-Shan Lu (a), Kee-hung Lai (b), T.C.E. Cheng (b) Keywords: Internet services; Liner shipping; Structural equation model Abstract: Operations research (OR) is the application of modeling techniques to formulate and analyze systems and problems for management decision-making. Structural equation modeling (SEM) is a modeling technique applied to social or behavioral systems to understand and explain relationships that may exist among elements of systems. Recently, the measurement of unobservable variables has gained increasing attention in operations management (OM) research, and the OR discipline has begun to recognize the value of applying SEM to analyze behavioral-related OR problems. To provide OR researchers with a better understanding of the application of this useful statistical modeling technique, this paper presents a tutorial on the application of SEM. Specifically, we investigate the key factors that affect the adoption of Internet services in the context of liner shipping services. Although [Fishbein, M.A., Ajzen, I., 1975. Belief, Attitude, Intention and Behavior: An Introduction to Theory and Research, Addison-Wesley, Reading, MA; Davis, F.D., 1989. Perceived usefulness, perceived ease of use, and user acceptance of information technology. MIS Quarterly 13 (3), 319-339; Ajzen, I., 1985. From intention to actions: A theory of planned behavior. In: Kuhl, J., Bechmann, J. (Eds.), Action Control: From Cognition to Behavior. Springer Verlag, New York, pp. 11-39; Ajzen, I., 1991. The theory of planned behavior. Organizational Behavior and Human Decision Processes 50, 179-211] have made important contributions to understanding users' behavior of technology acceptance, shippers' resistance to end-user systems is still a common problem in the liner shipping industry. To better predict, explain, and increase shippers' acceptance of technology, we need to understand why shippers accept or reject Internet services provided by their liner shipping carriers. Another objective of this paper is to propose and empirically test a theoretical framework that relates the intention of shippers to use Internet services in liner shipping with its antecedents such as perceived usefulness, perceived ease of use, and the perceptions of security protection. Tests of the structural model confirm Davis's (1989) notion that perceived ease of use explains the intention of shippers to use Internet services, and that perceived ease of use has a strong positive effect on perceived usefulness. The results also indicate that security protection influences perceived ease of use. The SEM analyses in this study offer OR researchers a methodological guide on how to assess the efficacy of both a measurement model that relates observed indicators to latent factors and a structural model that poses relationships between constructs. Author Affiliation: (a) Department of Transportation and Communication Management Science, National Cheng Kung University, No. 1, University Road, Tainan City 701, Taiwan, ROC (b) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong Article History: Received 5 March 2005; Accepted 2 May 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.01.025 Byline: J.J. Yuan (a), Y.X. Lin (a), C.T. Ng (b), T.C.E. Cheng (b) Keywords: Scheduling; Single machine; Fixed jobs; Precedence constraints Abstract: We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1- [delta])n-approximation algorithm exists even if all the release dates are zero, for any constant [delta] 0, if P[not equal to]NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2- [delta])-approximation algorithm, for any constant [delta] 0, if P[not equal to]NP, and for the weighted version, we show that the problem has no polynomial-time 2.sup.q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem. Author Affiliation: (a) Department of Mathematics, Zhengzhou University, Zhengzhou 450052, People's Republic of China (b) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China Article History: Received 4 March 2005; Accepted 13 January 2006

The analysis of the approximability of the schedules of fixed jobs on a single machine in a flowshop, subject to precedence constraints, is presented.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.09.006 Byline: Min Ji (a)(b)(c), Yong He (b), T.C.E. Cheng (c) Keywords: Single machine scheduling; Batch delivery cost; Optimal algorithm; Computational complexity Abstract: We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B, the problem remains strongly NP-hard when B a[c]1/2 U for a variable U [greater than or equal to]2 or B [greater than or equal to] U for any constant U [greater than or equal to]2. For the case of B a[c]1/2 U, we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant U [greater than or equal to]2. Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal. Author Affiliation: (a) College of Computer Science & Information Engineering, Zhejiang Gongshang University, Hangzhou 310035, PR China (b) Department of Mathematics, State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, PR China (c) Department of Logistics, The Hong Kong Polytechnic University, Kowloon, Hong Kong Article History: Received 25 October 2004; Accepted 2 September 2005

Computational complexity of derivation of optimal algorithm for scheduling of jobs on single machine, based on batch delivery cost, in a manufacturing firm, is discussed.

Optimality properties of Lawler's pseudo-polynomial algorithm to examine single machine total tardiness problem are presented.

A heuristic approach, which examines the single machine scheduling problem with resource dependent release times and processing times, is presented.

The problems of completing a job in a batch on time using a single machine are examined. The methods that reduce the single machine, serial batching scheduling problem are presented.

A scheduling model with step-deteriorating processing times is presented with the flow time problem shown as NP-complete.

Priority intersections are road junctions where at least one stream of vehicles must yield absolutely to another stream of vehicles. Knowledge of the delay and queueing processes of minor roa vehicles at such intersections is important for the decision making of traffic planners. Stochastic of the processes at these types of intersections have been progressing incrementally, taking more re and complex interactions into account. Renewal-reward and Markov chain models have been used extensively in these models. Time dependency of traffic flow has also been taken into consideration, through discrete approximations and other simplifications. Although some field data verifications of models have been performed, more intensive field data collection and analysis could prove useful in defining and extending the range of usefulness of these models., The use of stochastic models of delay and capacity in analyzing traffic flow can improve vehicular traffic management. Field research shows that in light traffic conditions, stochastic models can give reasonable estimates of the delay in or capacity of minor vehicular movement. In heavy traffic conditions, models that consider time-varying aspects of the vehicle flow are more appropriate. A review of stochastic modelling of delay and capacity at unsignalized priority intersections is presented.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.02.014 Byline: J.J. Yuan (a)(b), T.C.E. Cheng (b), C.T. Ng (b) Keywords: Scheduling; Single-variable-resource; Total weighted completion time; NP-hardness Abstract: Baker and Nuttle [K.R. Baker, H.L.W. Nuttle, Sequencing independent jobs with a single resource, Naval Research Logistics Quarterly 27 (1980) 499-510] studied the following single-variable-resource scheduling problem: sequencing n jobs for processing by a single resource to minimize a function of job completion times, when the availability of the resource varies over time. When the objective function to be minimized is the total weighted completion time, Baker and Nuttle conjectured that the problem is NP-hard. We show in this note that the conjecture is true. Author Affiliation: (a) Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China (b) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, People's Republic of China Article History: Received 24 November 2005; Accepted 14 February 2006

The solutions for single-variable-resource scheduling problems with relation to job completion time minimization are presented.

A new and tight lower bound on the mean completion time for optimal job sequences was derived for the completion time variance problem. The latter, an NP-hard problem that arises in a manufacturing environment, involves the scheduling of jobs with different processing times on a single machine under the constraints that job splitting and preemption are not permitted.