Abstract
The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
A. Bachman and A. Janiak,Scheduling jobs with position-dependent processing times, Journal of the Operational Research Society55 (2004), 257–264.
A. B. Badiru,Computational survey of univariate and multivariate learning curve models, IEEE Transactions on Engineering Management39 (1992), 176–188.
D. Biskup,Single-machine scheduling with learning considerations, European Journal of Operational Research115 (1999), 173–178.
J. R. Dejong,The effects of increasing skill on cycle time and its consequences for time standards, Ergonomics1 (1957), 51–60.
R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan,Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics5 (1979), 287–326.
S. M. Johnson,Optimal two and three stage production schedules with setup times included, Naval Research Logistics Quarterly1 (1954), 61–68.
G. Mosheiov,Scheduling problems with a learning effect, European Journal of Operational Research132 (2001), 687–693.
G. Mosheiov,Parallel machine scheduling with a learning effect, Journal of the Operational Research Society52 (2001), 1165–1169.
G. Mosheiov and J. B. Sidney,Scheduling with general job-dependent learning curves, European Journal of Operational Research147 (2003), 665–670.
C. C. Pegels,On start-up or learning curves: an expanded view, AIIE Transactions1 (1969), 316–322.
M. Pinedo,Scheduling: Theory, Algorithms and Systems, Prentice hall, Englewood cliffs, New jersey, 1995.
J.-B. Wang and Z.-Q. Xia,Flow shop scheduling with a learning effect, Journal of the Operational Research Society (to appear).
J.-B. Wang and Z.-Q. Xia,No-wait or no-idle permutation flowshop scheduling with dominating machines, J. Appl. Math. & Computing (to appear).
T. P. Wright,Factors affecting the cost of airplanes, Journal of the Aeronautical Sciences3 (1936), 122–128.
Author information
Authors and Affiliations
Corresponding author
Additional information
Ji-Bo Wang is an assistant professor at the Department of Science at Shenyang Institute of Aeronautical Engineering. He is a Ph. D student at Dalian University of Technology. Mr. Wang's research interests are the scheduling problems and operations research methods and applications.
Rights and permissions
About this article
Cite this article
Wang, JB. Flow shop scheduling jobs with position-dependent processing times. JAMC 18, 383–391 (2005). https://doi.org/10.1007/BF02936581
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02936581