Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2010.06.002 Byline: Dan Wang (a), Ming-Zheng Wang (b), Ji-Bo Wang (a)(c) Keywords: Scheduling; Single-machine; Learning effect; Resource allocation Abstract: We consider resource allocation scheduling with learning effect in which the processing time of a job is a function of its position in a sequence and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We analyse the problem with two different processing time functions. For each combination of these, we provide a polynomial time algorithm to find the optimal job sequence and resource allocation. Author Affiliation: (a) Operations Research and Cybernetics Institute, School of Science, Shenyang Aerospace University, Shenyang 110136, China (b) School of Management, Dalian University of Technology, Dalian 116024, China (c) Knowledge Management and Innovation Research Centre, Xi'an Jiaotong University, Xi'an 710049, China Article History: Received 6 January 2010; Revised 2 June 2010; Accepted 3 June 2010 Article Note: (footnote) [star] This manuscript was processed by Area Editor T.C. Edwin Cheng.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ijpe.2010.01.021 Byline: Ling Wang (a), Lin-Yan Sun (a)(b)(c), Lin-Hui Sun (b)(d)(e), Ji-Bo Wang (b)(e)(f) Abstract: In this paper, we consider a three-machine permutation flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes makespan. This problem is well known NP-hard. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. Moreover, a heuristic algorithm is proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational experiments on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm. The analysis shows that the proposed heuristic algorithm performs effectively and efficiently. Author Affiliation: (a) Management School, Xi'an Jiaotong University, Xi'an 710049, People's Republic of China (b) The State Key Laboratory for Manufacturing System Engineering, Xi'an Jiaotong University, Xi'an 710049, People's Republic of China (c) The Key Laboratory of the Ministry of Education on Process Control and Efficiency, Xi'an Jiaotong University, Xi'an 710049, People's Republic of China (d) School of Business Administration, Xi'an University of Technology, Xi'an 710054, People's Republic of China (e) Knowledge Management and Innovation Research Centre, Xi'an Jiaotong University, Xi'an 710049, People's Republic of China (f) Operations Research and Cybernetics Institute, School of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110136, People's Republic of China Article History: Received 7 January 2009; Accepted 26 January 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2009.08.003 Byline: Xue Huang (a), Ji-Bo Wang (a), Li-Yan Wang (a)(b), Wen-Jun Gao (a), Xue-Ru Wang (a) Keywords: Scheduling; Single machine; Learning effect; Deteriorating jobs Abstract: In this paper we consider the single machine scheduling problems with time-dependent deterioration and exponential learning effect, i.e., the actual processing time of a job depends not only on the processing times of the jobs already processed but also on its scheduled position. We consider the following objective functions: the makespan, the sum of the [delta]th ([delta][greater than or equal to]0) power of job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the sum of the [delta]th power of job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. Author Affiliation: (a) Department of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110136, People's Republic of China (b) School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, People's Republic of China Article History: Received 16 January 2009; Revised 30 May 2009; Accepted 8 August 2009 Article Note: (footnote) [star] This manuscript was processed by Area Editor Imed Kacem.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2009.05.002 Byline: Ji-Bo Wang (a), Li-Li Liu (b) Keywords: Scheduling; Flow shop; Deteriorating jobs; Learning effect; Total completion time; Branch-and-bound algorithm Abstract: In this paper we consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions. Author Affiliation: (a) Operations Research and Cybernetics Institute, School of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110136, People's Republic of China (b) School of Science, Shanghai Second Polytechnic University, Shanghai 201209, People's Republic of China Article History: Received 21 February 2009; Accepted 4 May 2009 Article Note: (footnote) [star] This manuscript was processed by Area Editor T.C. Edwin Cheng.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2008.09.020 Byline: Ji-Bo Wang (a), Li-Li Liu (b) Keywords: Scheduling; Flow shop; Deteriorating jobs; Total completion time; Branch-and-bound algorithm; Heuristic algorithm Abstract: In this paper, we consider a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time is a decreasing function of its execution start time. A proportional linear decreasing deterioration function is assumed. The objective is to find a sequence that minimizes total completion time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented, which show that the heuristic algorithm effectively and efficiently in obtaining near-optimal solutions. Author Affiliation: (a) School of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110136, People's Republic of China (b) School of Science, Shanghai Second Polytechnic University, Shanghai 201209, People's Republic of China Article History: Received 23 March 2008; Revised 10 September 2008; Accepted 12 September 2008 Article Note: (footnote) [star] This manuscript was processed by Area Editor Maged M. Dessouky.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2008.01.017 Byline: Ji-Bo Wang Keywords: Scheduling; Single machine; Learning effect; Setup times Abstract: This paper studies the single-machine scheduling problem with time-dependent learning effect and setup times considerations. The time-dependent learning effect means that the processing time of a job is defined by a function of the total normal processing time of the already processed jobs. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. Author Affiliation: Department of Science, Shenyang Institute of Aeronautical Engineering, Shenyang, Liaoning 110136, People's Republic of China Article History: Received 27 April 2007; Revised 28 January 2008; Accepted 29 January 2008

This paper studies the single-machine scheduling problem with time-dependent learning effect and setup times considerations. The time-dependent learning effect means that the processing time of a job is defined by a function of the total normal processing time of the already processed jobs. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved in polynomial time, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. Keywords: Scheduling; Single machine; Learning effect; Setup times

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2005.08.008 Byline: Ji-Bo Wang Abstract: This paper considers the general, no-wait and no-idle flow shop scheduling problems with deteriorating jobs, respectively. By a deteriorating job, we mean that the processing time is a decreasing function of its execution starting time. The normal processing time proportional to its decreasing rate is assumed and some dominant relationships between machines can be satisfied. It is shown that for the problems to minimize the makespan or the weighted sum of completion time, polynomial algorithms still exist, although these problems are more complicated than the classical ones. When the objective is to minimize the maximum lateness, the solutions of a classical version may not hold. Author Affiliation: Department of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110034, People's Republic of China