In this paper, we investigate the problem of semi-on-line scheduling n jobs on m identical parallel machines under the assumption that the ordering of the jobs by processing time is known and the jobs have arbitrary r...In this paper, we investigate the problem of semi-on-line scheduling n jobs on m identical parallel machines under the assumption that the ordering of the jobs by processing time is known and the jobs have arbitrary release times. Our aim is to minimize the maximum completion time. An ordinal algorithm is investigated and its worst case ratio is analyzed.展开更多
Active schedule is one of the most basic and popular concepts in production scheduling research. For identical parallel machine scheduling with jobs＇ dynamic arrivals, the tight performance bounds of active schedules...Active schedule is one of the most basic and popular concepts in production scheduling research. For identical parallel machine scheduling with jobs＇ dynamic arrivals, the tight performance bounds of active schedules under the measurement of four popular objectives are respectively given in this paper. Similar analysis method and conclusions can be generalized to static identical parallel machine and single machine scheduling problem.展开更多
This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service ...This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.展开更多
In this paper, we investigate the/-preemptive scheduling on parallel machines to maximize the minimum machine completion time, i.e., machine covering problem with limited number of preemptions. It is aimed to obtain t...In this paper, we investigate the/-preemptive scheduling on parallel machines to maximize the minimum machine completion time, i.e., machine covering problem with limited number of preemptions. It is aimed to obtain the worst case ratio of the objective value of the optimal schedule with unlimited preemptions and that of the schedule allowed to be preempted at most i times. For the m identical machines case, we show the worst case ratio is 2m-i-1/m and we present a polynomial time algorithm which can guarantee the ratio for any 0 〈 i 〈2 m - 1. For the /-preemptive scheduling on two uniform machines case, we only need to consider the cases of i = 0 and i = 1. For both cases, we present two linear time algorithms and obtain the worst case ratios with respect to s, i.e., the ratio of the speeds of two machines.展开更多
This paper considers parallel machine scheduling with special jobs. Normal jobs can be processed on any of the parallel machines, while the special jobs can only be processed on one machine. The problem is analyzed fo...This paper considers parallel machine scheduling with special jobs. Normal jobs can be processed on any of the parallel machines, while the special jobs can only be processed on one machine. The problem is analyzed for various manufacturing conditions and service requirements. The off-line scheduling problem is transformed into a classical parallel machine scheduling problem. The on-line scheduling uses the FCFS （first come, first served）, SWSC （special window for special customers）, and FFFS （first fit, first served） algorithms to satisfy the various requirements. Furthermore, this paper proves that FCFS has a competitive ratio of m, where m is the number of parallel machines, and this bound is asymptotically tight, SWSC has a competitive ratio of 2 and FFFS has a competitive ratio of 3- 2/m, and these bounds are tight.展开更多
This paper considers the semi-resumable model of single machine scheduling with anon-availability period. The machine is not available for processing during a given time interval.A job cannot be completed before the n...This paper considers the semi-resumable model of single machine scheduling with anon-availability period. The machine is not available for processing during a given time interval.A job cannot be completed before the non-availability period will have to partially restartafter the machine has become available again. For the problem with objective of minimizingmakespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed.For the problem with objective of minimizing total weighted completion time, an approximationalgorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latterproblem are also considered, and improved algorithms are given.展开更多
This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT a...This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems, The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.展开更多
Focusing on the ordinal scheduling problem on a parallel machine system, we discuss the background of ordinal scheduling and the motivation of ordinal algorithms. In addition, for the ordinal scheduling problem on ide...Focusing on the ordinal scheduling problem on a parallel machine system, we discuss the background of ordinal scheduling and the motivation of ordinal algorithms. In addition, for the ordinal scheduling problem on identical parallel machines with the objective to maximize the minimum machine load, we then give two asymptotically optimal algorithm classes which have worst-case ratios very close to the upper bound of the problem for any given m. These results greatly improve the results proposed by He Yong and Tan Zhiyi in 2002.展开更多
In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off\|line or on\|line environment. But in practice, problems are often not really off\|line or on\|line but someh...In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off\|line or on\|line environment. But in practice, problems are often not really off\|line or on\|line but somehow in between. This means that, with respect to the on\|line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on\|line ones. The authors studied two semi on\|line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.展开更多
This paper studies the hybrid flow-shop scheduling problem with no-wait restrictions. The production process consists of two machine centers, one has a single machine and the other has more than one parallel machine....This paper studies the hybrid flow-shop scheduling problem with no-wait restrictions. The production process consists of two machine centers, one has a single machine and the other has more than one parallel machine. A greedy heuristic named least deviation algorithm is designed and its worst case performance is analyzed. Computational results are also given to show the algorithm's average performance compared with some other algorithms. The least deviation algorithm outperforms the others in most cases tested here, and it is of low computational complexity and is easy to carry out,thus it is of favorable application value.展开更多
This paper studies the coordination effects between stages for scheduling problems where decision-making is a two-stage process. Two stages are considered as one system. The system can be a supply chain that links two...This paper studies the coordination effects between stages for scheduling problems where decision-making is a two-stage process. Two stages are considered as one system. The system can be a supply chain that links two stages, one stage representing a manufacturer; and the other, a distributor It also can represent a single manufacturer, while each stage represents a different department responsible for a part of operations. A problem that jointly considers both stages in order to achieve ideal overall system performance is defined as a system problem. In practice, at times, it might not be feasible for the two stages to make coordinated decisions due to (i) the lack of channels that allow decision makers at the two stages to cooperate, and/or (ii) the optimal solution to the system problem is too difficult (or costly) to achieve.Two practical approaches are applied to solve a variant of two-stage logistic scheduling problems. The Forward Approach is defined as a solution procedure by which the first stage of the system problem is solved first, followed by the second stage. Similarly, the Backward Approach is defined as a solution procedure by which the second stage of the system problem is solved prior to solving the first stage. In each approach, two stages are solved sequentially and the solution generated is treated as a heuristic solution with respect to the corresponding system problem. When decision makers at two stages make decisions locally without considering consequences to the entire system, ineffectiveness may result - even when each stage optimally solves its own problem. The trade-off between the time complexity and the solution quality is the main concern. This paper provides the worst-case performance analysis for each approach.展开更多
In this paper, we consider a uniform machine scheduling problem with nonsimultaneous available times. We prove that LPT algorithm has a worst case bound in the interval (1.52,5/3). We tighten this bound when the machi...In this paper, we consider a uniform machine scheduling problem with nonsimultaneous available times. We prove that LPT algorithm has a worst case bound in the interval (1.52,5/3). We tighten this bound when the machine speed ratio is small or m=2. Furthermore, we present a linear compound algorithm QLC with a worst case bound of 6/5 for a two-machine system.展开更多
This paper describes a heuristic for solving F3/bi = b/Cmax scheduling problem. This algorithm first uses the Johnson’s algorithm solving F2Cmax, then, presents revised algorithm to solve F3/bi = b/Cmax. Lastly, an O...This paper describes a heuristic for solving F3/bi = b/Cmax scheduling problem. This algorithm first uses the Johnson’s algorithm solving F2Cmax, then, presents revised algorithm to solve F3/bi = b/Cmax. Lastly, an O(n log n) time heuristic is presented which generates a schedule with length at most 3/2 times that of an optimal schedule, for even number n 4, and 3/2 + 1/(2n) times that of an optimal schedule, for odd number n 4. These bounds are tight.展开更多
文摘In this paper, we investigate the problem of semi-on-line scheduling n jobs on m identical parallel machines under the assumption that the ordering of the jobs by processing time is known and the jobs have arbitrary release times. Our aim is to minimize the maximum completion time. An ordinal algorithm is investigated and its worst case ratio is analyzed.
基金This work was supported by the National Natural Science Foundation of China (No. 60474002, 60504026)Shanghai Development Foundation forScience and Technology (No. 04DZ11008)
文摘Active schedule is one of the most basic and popular concepts in production scheduling research. For identical parallel machine scheduling with jobs＇ dynamic arrivals, the tight performance bounds of active schedules under the measurement of four popular objectives are respectively given in this paper. Similar analysis method and conclusions can be generalized to static identical parallel machine and single machine scheduling problem.
基金Project supported by the National Natural Science Foundation of China (No. 10271110) and the Teaching and Research Award Pro-gram for Outstanding Young Teachers in Higher Education, Institu-tions of MOE, China
文摘This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.
基金Supported by the National Natural Science Foundation of China(11001242,11071220)
文摘In this paper, we investigate the/-preemptive scheduling on parallel machines to maximize the minimum machine completion time, i.e., machine covering problem with limited number of preemptions. It is aimed to obtain the worst case ratio of the objective value of the optimal schedule with unlimited preemptions and that of the schedule allowed to be preempted at most i times. For the m identical machines case, we show the worst case ratio is 2m-i-1/m and we present a polynomial time algorithm which can guarantee the ratio for any 0 〈 i 〈2 m - 1. For the /-preemptive scheduling on two uniform machines case, we only need to consider the cases of i = 0 and i = 1. For both cases, we present two linear time algorithms and obtain the worst case ratios with respect to s, i.e., the ratio of the speeds of two machines.
基金Supported by the National Natural Science Foundation of China (No.70471008)
文摘This paper considers parallel machine scheduling with special jobs. Normal jobs can be processed on any of the parallel machines, while the special jobs can only be processed on one machine. The problem is analyzed for various manufacturing conditions and service requirements. The off-line scheduling problem is transformed into a classical parallel machine scheduling problem. The on-line scheduling uses the FCFS （first come, first served）, SWSC （special window for special customers）, and FFFS （first fit, first served） algorithms to satisfy the various requirements. Furthermore, this paper proves that FCFS has a competitive ratio of m, where m is the number of parallel machines, and this bound is asymptotically tight, SWSC has a competitive ratio of 2 and FFFS has a competitive ratio of 3- 2/m, and these bounds are tight.
基金Supported by the National Natural Science Foundation of China(10971191, 60021201)Fundamental Research Funds for the Central Universities(2010QNA3040)the China Postdoctoral Science Foundation
文摘This paper considers the semi-resumable model of single machine scheduling with anon-availability period. The machine is not available for processing during a given time interval.A job cannot be completed before the non-availability period will have to partially restartafter the machine has become available again. For the problem with objective of minimizingmakespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed.For the problem with objective of minimizing total weighted completion time, an approximationalgorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latterproblem are also considered, and improved algorithms are given.
基金the National Natural Science Foundation of China(10301028,60021201)A preliminary version of this paper appeared in the proceedings of the 1st International Conference on Algorithmic Applications in Management,Lecture Notes in Computer Science 3521
文摘This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems, The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.
文摘Focusing on the ordinal scheduling problem on a parallel machine system, we discuss the background of ordinal scheduling and the motivation of ordinal algorithms. In addition, for the ordinal scheduling problem on identical parallel machines with the objective to maximize the minimum machine load, we then give two asymptotically optimal algorithm classes which have worst-case ratios very close to the upper bound of the problem for any given m. These results greatly improve the results proposed by He Yong and Tan Zhiyi in 2002.
文摘In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off\|line or on\|line environment. But in practice, problems are often not really off\|line or on\|line but somehow in between. This means that, with respect to the on\|line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on\|line ones. The authors studied two semi on\|line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.
基金Supported by the National Natural Science Foundationof China( No. 6 990 40 0 7)
文摘This paper studies the hybrid flow-shop scheduling problem with no-wait restrictions. The production process consists of two machine centers, one has a single machine and the other has more than one parallel machine. A greedy heuristic named least deviation algorithm is designed and its worst case performance is analyzed. Computational results are also given to show the algorithm's average performance compared with some other algorithms. The least deviation algorithm outperforms the others in most cases tested here, and it is of low computational complexity and is easy to carry out,thus it is of favorable application value.
文摘This paper studies the coordination effects between stages for scheduling problems where decision-making is a two-stage process. Two stages are considered as one system. The system can be a supply chain that links two stages, one stage representing a manufacturer; and the other, a distributor It also can represent a single manufacturer, while each stage represents a different department responsible for a part of operations. A problem that jointly considers both stages in order to achieve ideal overall system performance is defined as a system problem. In practice, at times, it might not be feasible for the two stages to make coordinated decisions due to (i) the lack of channels that allow decision makers at the two stages to cooperate, and/or (ii) the optimal solution to the system problem is too difficult (or costly) to achieve.Two practical approaches are applied to solve a variant of two-stage logistic scheduling problems. The Forward Approach is defined as a solution procedure by which the first stage of the system problem is solved first, followed by the second stage. Similarly, the Backward Approach is defined as a solution procedure by which the second stage of the system problem is solved prior to solving the first stage. In each approach, two stages are solved sequentially and the solution generated is treated as a heuristic solution with respect to the corresponding system problem. When decision makers at two stages make decisions locally without considering consequences to the entire system, ineffectiveness may result - even when each stage optimally solves its own problem. The trade-off between the time complexity and the solution quality is the main concern. This paper provides the worst-case performance analysis for each approach.
基金the National 973 Fundamental Research Project of Chinathe National Natural Sciences Foundation of China!19701028
文摘In this paper, we consider a uniform machine scheduling problem with nonsimultaneous available times. We prove that LPT algorithm has a worst case bound in the interval (1.52,5/3). We tighten this bound when the machine speed ratio is small or m=2. Furthermore, we present a linear compound algorithm QLC with a worst case bound of 6/5 for a two-machine system.
文摘This paper describes a heuristic for solving F3/bi = b/Cmax scheduling problem. This algorithm first uses the Johnson’s algorithm solving F2Cmax, then, presents revised algorithm to solve F3/bi = b/Cmax. Lastly, an O(n log n) time heuristic is presented which generates a schedule with length at most 3/2 times that of an optimal schedule, for even number n 4, and 3/2 + 1/(2n) times that of an optimal schedule, for odd number n 4. These bounds are tight.
